tutorial

Euclidean Steiner Shallow-Light Trees

Author:

Shay SolomonAuthors Info & Claims

SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

Pages 454 - 463

https://doi.org/10.1145/2582112.2582160

Published: 08 June 2014 Publication History

Abstract

A spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree is called a shallow-light tree (shortly, SLT). More specifically, an (α, β)-SLT of a weighted undirected graph G = (V, E, w) with respect to a designated vertex rt ∈ V is a spanning tree of G with:

(1) root-stretch α -- it preserves all distances between rt and the other vertices up to a factor of α.

(2) lightness β -- it has weight at most β times the weight of a minimum spanning tree MST(G) of G.

Tight tradeoffs between the parameters of SLTs were established by Awerbuch et al. in PODC'90 and by Khuller et al. in SODA'93. They showed that for any ϵ > 0, any graph admits a (1 + ϵ, O(1/ϵ))-SLT with respect to any root vertex, and complemented this result with a matching lower bound.

Khuller et al. asked if the upper bound β = O(1/ϵ) on the lightness of SLTs can be improved in constant-dimensional Euclidean spaces. In FOCS'11 Elkin and this author gave a negative answer to this question, showing a lower bound of β = Ω(1/ϵ) that applies to 2-dimensional Euclidean spaces.

In this paper we show that Steiner points lead to a quadratic improvement in Euclidean SLTs, by presenting a construction of Euclidean Steiner (1 + ϵ, O(√1/ϵ))-SLTs. While the lightness bound β O(√1/ϵ) of our construction applies to Euclidean spaces of any constant dimension, there is a matching lower bound of β Ω(√1/ϵ) even in 2-dimensional Euclidean spaces. The runtime of our construction, and thus the number of Steiner points used, are bounded by O(n).

References

[1]

N. Alon, R. M. Karp, D. Peleg, and D. B. West. A graph-theoretic game and its application to the k-server problem. SIAM J. Comput., 24(1):78--100, 1995.

Digital Library

[2]

C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, and D. Karger. Prim-Dijkstra tradeoffs for improved performance-driven routing tree design. IEEE Trans. on CAD of Integrated Circuits and Systems, 14(7):890--896, 1995.

Digital Library

[3]

B. Aronov, M. de Berg, O. Cheong, J. Gudmundsson, H. J. Haverkort, M. H. M. Smid, and A. Vigneron. Sparse geometric graphs with small dilation. Comput. Geom., 40(3):207--219, 2008.

Digital Library

[4]

B. Awerbuch, A. Baratz, and D. Peleg. Cost-sensitive analysis of communication protocols. In Proc. of 9th PODC, pages 177--187, 1990.

Digital Library

[5]

B. Awerbuch, A. Baratz, and D. Peleg. Efficient broadcast and light-weight spanners. Manuscript, 1991.

[6]

Y. Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In Proc. of 37th FOCS, pages 184--193, 1996.

Digital Library

[7]

Y. Bartal. On approximating arbitrary metrices by tree metrics. In Proc. of 30th STOC, pages 161--168, 1998.

Digital Library

[8]

Y. Ben-Shimol, A. Dvir, and M. Segal. SPLAST: a novel approach for multicasting in mobile wireless ad hoc networks. In Proc. of 15th PIMRC, pages 1011--1015, 2004.

[9]

R. Braynard, D. Kostic, A. Rodriguez, J. Chase, and A. Vahdat. Opus: an overlay peer utility service. In Prof. of 5th OPENARCH, 2002.

[10]

P. Carmi and L. Chaitman-Yerushalmi. Unexplored steiner ratios in geometric networks. In Proc. of 18th COCOON, pages 275--286, 2012.

[11]

T. M. Chan. Well-separated pair decomposition in linear time? Inf. Process. Lett., 107(5):138--141, 2008.

Digital Library

[12]

M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li. Approximation algorithms for directed Steiner problems. J. Algorithms, 33(1):73--91, 1999.

Digital Library

[13]

F. Chung and R. Graham. A new bound for euclidean steiner minimal trees. Annals of the New York Academy of Sciences, 440(1):328--346, 1985.

[14]

J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong. Performance-driven global routing for cell based ics. In Proc. of 9th ICCD, pages 170--173, 1991.

Digital Library

[15]

J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong. Provably good algorithms for performance-driven global routing. In Proc. of 5th ISCAS, pages 2240--2243, 1992.

[16]

J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong. Provably good performance-driven global routing. IEEE Trans. on CAD of Integrated Circuits and Sys., 11(6):739--752, 1992.

Digital Library

[17]

R. Cristescu, B. Beferull-Lozano, M. Vetterli, and R. Wattenhofer. Network correlated data gathering with explicit communication: NP-completeness and algorithms. IEEE/ACM Trans. Netw., 14(1):41--54, 2006.

Digital Library

[18]

Y. Dinitz, M. Elkin, and S. Solomon. Low-light trees, and tight lower bounds for Euclidean spanners. Discrete & Computational Geometry, 43(4):736--783, 2010.

Digital Library

[19]

M. Elkin and S. Solomon. Narrow-shallow-low-light trees with and without Steiner points. SIAM J. Discrete Math., 25(1):181--210, 2011.

Digital Library

[20]

M. Elkin and S. Solomon. Steiner shallow-light trees are exponentially lighter than spanning ones. In Proc. of 52nd FOCS, pages 373--382, 2011. The journal version of this paper is currently under review.

Digital Library

[21]

J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proc. of 35th STOC, pages 448--455, 2003.

Digital Library

[22]

E. N. Gilbert and H. O. Pollak. Steiner minimal trees. SIAM J. Applied Math., 16(1):1--29, 1968.

[23]

A. Goel and K. Munagala. Balancing Steiner trees and shortest path trees online. In Proc. of 11th SODA, pages 562--563, 2000.

Digital Library

[24]

A. Gupta. Steiner points in tree metrics don't (really) help. In Proc. of 12th SODA, pages 220--227, 2001.

Digital Library

[25]

M. T. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour. Approximating buy-at-bulk and shallow-light k-Steiner trees. Algorithmica, 53(1):89--103, 2009.

Digital Library

[26]

A. O. Ivanov and A. A. Tuzhilin. The Steiner Ratio Gilbert-Pollak Conjecture Is Still Open - Clarification Statement. Algorithmica, 62(1-2), 630--632, 2012.

Digital Library

[27]

X. Jia, D.-Z. Du, X.-D. Hu, M.-K. Lee, and J. Gu. Optimization of wavelength assignment for QoS multicast in WDM networks. IEEE Transactions on Communications, 49(2):341--350, 2001.

[28]

S. Khuller, B. Raghavachari, and N. E. Young. Balancing minimum spanning and shortest path trees. In Proc. of 4th SODA, pages 243--250, 1993.

Digital Library

[29]

P. N. Klein, S. Rao, M. Rauch, and S. Subramanian. Faster shortest-path algorithms for planar graphs. In Proc. of 26th STOC, pages 27--37, 1994.

Digital Library

[30]

V. P. Kompella, J. Pasquale, and G. C. Polyzos. Multicast routing for multimedia communication. IEEE/ACM Trans. Netw., 1(3):286--292, 1993.

Digital Library

[31]

G. Konjevod, R. Ravi, and F. S. Salman. On approximating planar metrics by tree metrics. Inf. Process. Lett., 80(4):213--219, 2001.

[32]

G. Kortsarz and D. Peleg. Approximating the weight of shallow Steiner trees. Discrete Applied Mathematics, 93(2-3):265--285, 1999.

Digital Library

[33]

D. Kostic and A. Vahdat. Latency versus cost optimizations in hierarchical overlay networks. Technical report, Duke University, (CS-2001-04), 2002.

[34]

W. Liang and Y. Liu. Online data gathering for maximizing network lifetime in sensor networks. IEEE Trans. Mob. Comput., 6(1):2--11, 2007.

Digital Library

[35]

H. Luo, J. Luo, Y. Liu, and S. K. Das. Adaptive data fusion for energy efficient routing in wireless sensor networks. IEEE Trans. Computers, 55(10):1286--1299, 2006.

Digital Library

[36]

M. V. Marathe, R. Ravi, R. Sundaram, S. S. Ravi, D. J. Rosenkrantz, and H. B. Hunt III. Bicriteria network design problems. J. Algorithms, 28(1):142--171, 1998.

Digital Library

[37]

J. Naor and B. Schieber. Improved approximations for shallow-light spanning trees. In Proc. of 38th FOCS, pages 536--541, 1997.

Digital Library

[38]

D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia, PA, 2000.

[39]

F. S. Salman, J. Cheriyan, R. Ravi, and S. Subramanian. Buy-at-bulk network design: Approximating the single-sink edge installation problem. In Proc. of 8th SODA, pages 619--628, 1997.

Digital Library

[40]

A. Shaikh and K. G. Shin. Destination-driven routing for low-cost multicast. IEEE Journal on Selected Areas in Communications, 15(3):373--381, 1997.

Digital Library

[41]

H. Shpungin and M. Segal. Near optimal multicriteria spanner constructions in wireless ad-hoc networks. IEEE/ACM Transactions on Networking, 18(6):1963--1976, 2010.

Digital Library

[42]

J. Vogel, J. Widmer, D. Farin, M. Mauve, and W. Effelsberg. Priority-based distribution trees for application-level multicast. In Proc. of 2nd NETGAMES, pages 148--157, 2003.

Digital Library

[43]

P. von Rickenbach and R. Wattenhofer. Gathering correlated data in sensor networks. In Proc. of DIALM-POMC, pages 60--66, 2004.

Digital Library

[44]

B. Y. Wu, K.-M. Chao, and C. Y. Tang. Light graphs with small routing cost. Networks, 39(3):130--138, 2002.

Cited By

Filtser ALe HLeonardi SGupta A(2022)Locality-sensitive orderings and applications to reliable spannersProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520042(1066-1079)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520042
Chen GYoung E(2020)SALT: Provably Good Routing Topology by a Novel Steiner Shallow-Light Tree AlgorithmIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2019.289465339:6(1217-1230)Online publication date: Jun-2020
https://doi.org/10.1109/TCAD.2019.2894653
Le HSolomon S(2019)Truly Optimal Euclidean Spanners2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2019.00069(1078-1100)Online publication date: Nov-2019
https://doi.org/10.1109/FOCS.2019.00069

Index Terms

Euclidean Steiner Shallow-Light Trees
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones
FOCS '11: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science

For a pair of parameters $\alpha,\beta \ge 1$, a spanning tree $T$ of a weighted undirected $n$-vertex graph $G = (V,E,w)$ is called an \emph{$(\alpha,\beta)$-shallow-light tree} (shortly, $(\alpha,\beta)$-SLT)of $G$ with respect to a designated vertex $...
Narrow-Shallow-Low-Light Trees with and without Steiner Points

We show that for every set $\mathcal{S}$ of $n$ points in the plane and a designated point $rt\in\mathcal{S}$, there exists a tree $T$ that has small maximum degree, depth, and weight. Moreover, for every point $v\in\mathcal{S}$, the distance between $...
Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees

We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V,E) with a set of terminals T⊆V including a particular vertex s called the root, and an integer k≤|T|. There are two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

June 2014

588 pages

ISBN:9781450325943

DOI:10.1145/2582112

Program Chairs:
Siu-Wing Cheng
HKUST
,
Olivier Devillers
INRIA

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Tutorial
Research
Refereed limited

Conference

SOCG'14

SOCG'14: Annual Symposium on Computational Geometry

June 8 - 11, 2014

Kyoto, Japan

Acceptance Rates

SOCG'14 Paper Acceptance Rate 60 of 175 submissions, 34%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
153
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)2

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Filtser ALe HLeonardi SGupta A(2022)Locality-sensitive orderings and applications to reliable spannersProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520042(1066-1079)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520042
Chen GYoung E(2020)SALT: Provably Good Routing Topology by a Novel Steiner Shallow-Light Tree AlgorithmIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2019.289465339:6(1217-1230)Online publication date: Jun-2020
https://doi.org/10.1109/TCAD.2019.2894653
Le HSolomon S(2019)Truly Optimal Euclidean Spanners2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2019.00069(1078-1100)Online publication date: Nov-2019
https://doi.org/10.1109/FOCS.2019.00069

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents