Near-optimal light spanners
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Near-optimal light spanners. / Chechik, Shiri; Wulff-Nilsen, Christian.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2016. p. 883-892.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Near-optimal light spanners
AU - Chechik, Shiri
AU - Wulff-Nilsen, Christian
PY - 2016
Y1 - 2016
N2 - A spanner if of a weighted undirected graph G is a "sparse" subgraph that approximately preserves distances between every pair of vertices in G. We refer to if as a δ-spanner of G for some parameter δ ≥ 1 if the distance in H between every vertex pair is at most a factor δ bigger than in G. In this case, we say that H has stretch δ. Two main measures of the sparseness of a spanner are the size (number of edges) and the total weight (the sum of weights of the edges in the spanner). It is well-known that for any positive integer k, one can efficiently construct a (2k-l)-spanner of G with 0(n1+1/k) edges where n is the number of vertices [2]. This size-stretch tradeoff is conjectured to be optimal based on a girth conjecture of Erdös [17]. However, the current state of the art for the second measure is not yet optimal. Recently Elkin, Neiman and Solomon [ICALP 14] presented an improved analysis of the greedy algorithm, proving that the greedy algorithm admits (2k-1) · (1 + ∈) stretch and total edge weight of Oc((k/logk) · ω(MST(G)) · n1/k), where ω(MST(G)) is the weight of a minimum spanning tree of G. The previous analysis by Chandra et al. [SOCG 92] admitted (2k-1) · (1 + ∈) stretch and total edge weight of Ot(kω(MST(G))nl/k). Hence, Elkin et al. improved the weight of the spanner by a log k factor. In this work, we complectly remove the k factor from the weight, presenting a spanner with (2k-1) · (1 + ∈) stretch, O∈(ω(MST(G))n1/k) total weight, and O(n1+1/k) edges. Up to a (1 + ∈) factor in the stretch this matches the girth conjecture of Erdös [17].
AB - A spanner if of a weighted undirected graph G is a "sparse" subgraph that approximately preserves distances between every pair of vertices in G. We refer to if as a δ-spanner of G for some parameter δ ≥ 1 if the distance in H between every vertex pair is at most a factor δ bigger than in G. In this case, we say that H has stretch δ. Two main measures of the sparseness of a spanner are the size (number of edges) and the total weight (the sum of weights of the edges in the spanner). It is well-known that for any positive integer k, one can efficiently construct a (2k-l)-spanner of G with 0(n1+1/k) edges where n is the number of vertices [2]. This size-stretch tradeoff is conjectured to be optimal based on a girth conjecture of Erdös [17]. However, the current state of the art for the second measure is not yet optimal. Recently Elkin, Neiman and Solomon [ICALP 14] presented an improved analysis of the greedy algorithm, proving that the greedy algorithm admits (2k-1) · (1 + ∈) stretch and total edge weight of Oc((k/logk) · ω(MST(G)) · n1/k), where ω(MST(G)) is the weight of a minimum spanning tree of G. The previous analysis by Chandra et al. [SOCG 92] admitted (2k-1) · (1 + ∈) stretch and total edge weight of Ot(kω(MST(G))nl/k). Hence, Elkin et al. improved the weight of the spanner by a log k factor. In this work, we complectly remove the k factor from the weight, presenting a spanner with (2k-1) · (1 + ∈) stretch, O∈(ω(MST(G))n1/k) total weight, and O(n1+1/k) edges. Up to a (1 + ∈) factor in the stretch this matches the girth conjecture of Erdös [17].
U2 - 10.1137/1.9781611974331.ch63
DO - 10.1137/1.9781611974331.ch63
M3 - Article in proceedings
AN - SCOPUS:84963652548
SP - 883
EP - 892
BT - Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
PB - Society for Industrial and Applied Mathematics
T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms
Y2 - 10 January 2016 through 12 January 2016
ER -
ID: 168285245