DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.11

Approximating the Norms of Graph Spanners

Authors: Eden Chlamtáč, Michael Dinitz, and Thomas Robinson

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract

The l_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 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.

Cite as

Eden Chlamtáč, Michael Dinitz, and Thomas Robinson. Approximating the Norms of Graph Spanners. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chlamtac_et_al:LIPIcs.APPROX-RANDOM.2019.11,
  author =	{Chlamt\'{a}\v{c}, Eden and Dinitz, Michael and Robinson, Thomas},
  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 =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.11},
  URN =		{urn:nbn:de:0030-drops-112261},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.11},
  annote =	{Keywords: Spanners, Approximations}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2019.40

The Norms of Graph Spanners

Authors: Eden Chlamtáč, Michael Dinitz, and Thomas Robinson

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract

A t-spanner of a graph G is a subgraph H in which all distances are preserved up to a multiplicative t factor. A classical result of Althöfer et al. is that for every integer k and every graph G, there is a (2k-1)-spanner of G with at most O(n^{1+1/k}) edges. But for some settings the more interesting notion is not the number of edges, but the degrees of the nodes. This spurred interest in and study of spanners with small maximum degree. However, this is not necessarily a robust enough objective: we would like spanners that not only have small maximum degree, but also have "few" nodes of "large" degree. To interpolate between these two extremes, in this paper we initiate the study of graph spanners with respect to the l_p-norm of their degree vector, thus simultaneously modeling the number of edges (the l_1-norm) and the maximum degree (the l_{infty}-norm). We give precise upper bounds for all ranges of p and stretch t: we prove that the greedy (2k-1)-spanner has l_p norm of at most max(O(n), O(n^{{k+p}/{kp}})), and that this bound is tight (assuming the Erdős girth conjecture). We also study universal lower bounds, allowing us to give "generic" guarantees on the approximation ratio of the greedy algorithm which generalize and interpolate between the known approximations for the l_1 and l_{infty} norm. Finally, we show that at least in some situations, the l_p norm behaves fundamentally differently from l_1 or l_{infty}: there are regimes (p=2 and stretch 3 in particular) where the greedy spanner has a provably superior approximation to the generic guarantee.

Cite as

Eden Chlamtáč, Michael Dinitz, and Thomas Robinson. The Norms of Graph Spanners. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chlamtac_et_al:LIPIcs.ICALP.2019.40,
  author =	{Chlamt\'{a}\v{c}, Eden and Dinitz, Michael and Robinson, Thomas},
  title =	{{The Norms of Graph Spanners}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{40:1--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.40},
  URN =		{urn:nbn:de:0030-drops-106163},
  doi =		{10.4230/LIPIcs.ICALP.2019.40},
  annote =	{Keywords: spanners, approximations}
}

Search Results

Documents authored by Robinson, Thomas

Approximating the Norms of Graph Spanners

Abstract

Cite as

The Norms of Graph Spanners

Abstract

Cite as

Thanks for your feedback!

Could not send message