License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.11
URN: urn:nbn:de:0030-drops-112261
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11226/
Go to the corresponding LIPIcs Volume Portal

Chlamtác, Eden ; Dinitz, Michael ; Robinson, Thomas

Approximating the Norms of Graph Spanners

pdf-format:
LIPIcs-APPROX-RANDOM-2019-11.pdf (0.6 MB)

Abstract

The l_p-norm of the degree vector was recently introduced by [Chlamtác, Dinitz, Robinson ICALP '19] as a new cost metric for graph spanners, as it interpolates between two traditional notions of cost (the sparsity l_1 and the max degree l_infty) 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 l_2-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.

BibTeX - Entry

@InProceedings{chlamtc_et_al:LIPIcs:2019:11226,
  author =	{Eden Chlamt{\'a}c and Michael Dinitz and Thomas Robinson},
  title =	{{Approximating the Norms of Graph Spanners}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11226},
  URN =		{urn:nbn:de:0030-drops-112261},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.11},
  annote =	{Keywords: Spanners, Approximations}
}

Keywords: Spanners, Approximations
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI