עדן כלמטץ'

The ℓ_p-norm of the degree vector was recently introduced by [Chlamtáč, Dinitz, Robinson ICALP’19] as a new cost metric for graph spanners, as it interpolates between two traditional notions of cost (the sparsity ℓ₁ and the max degree ℓ_∞) and is well-motivated from applications. We study this from an approximation algorithms point of view, analyzing old algorithms and designing new algorithms for this new context, as well as providing hardness results. Our main results are for the ℓ₂-norm and stretch 3, where we give a tight analysis of the greedy algorithm and a new algorithm specifically tailored to this setting which gives an improved approximation ratio.