More Web Proxy on the site http://driver.im/

research-article

The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree

Authors:

Jakub Oćwieja,

Marcin Pilipczuk,

Piotr Sankowski,

Anna ZychAuthors Info & Claims

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

Pages 11 - 20

https://doi.org/10.1145/2746539.2746615

Published: 14 June 2015 Publication History

Abstract

In this paper we study the Steiner tree problem over a dynamic set of terminals. We consider the model where we are given an n-vertex graph G=(V,E,w) with positive real edge weights, and our goal is to maintain a tree which is a good approximation of the minimum Steiner tree spanning a terminal set S ⊆ V, which changes over time. The changes applied to the terminal set are either terminal additions (incremental scenario), terminal removals (decremental scenario), or both (fully dynamic scenario). Our task here is twofold. We want to support updates in sublinear o(n) time, and keep the approximation factor of the algorithm as small as possible.

We show that we can maintain a (6+ε)-approximate Steiner tree of a general graph in ~O(√n log D) time per terminal addition or removal. Here, strecz denotes the stretch of the metric induced by G. For planar graphs we achieve the same running time and the approximation ratio of (2+ε). Moreover, we show faster algorithms for incremental and decremental scenarios. Finally, we show that if we allow higher approximation ratio, even more efficient algorithms are possible. In particular we show a polylogarithmic time (4+ε)-approximate algorithm for planar graphs.

One of the main building blocks of our algorithms are dynamic distance oracles for vertex-labeled graphs, which are of independent interest. We also improve and use the online algorithms for the Steiner tree problem.

References

[1]

I. Abraham, D. Malkhi, and D. Ratajczak. Compact multicast routing. In 23rd International Symposium on Distributed Computing (DISC 2009). Springer Verlag, September 2009.

Digital Library

[2]

E. Aharoni and R. Cohen. Restricted dynamic steiner trees for scalable multicast in datagram networks. In INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution., Proceedings IEEE, volume 2, pages 876--883 vol.2, Apr 1997.

Digital Library

[3]

E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. In In FOCS, pages 295--304, 2004.

Digital Library

[4]

S. Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753--782, 1998.

Digital Library

[5]

F. Bauer and A. Varma. ARIES: A rearrangeable inexpensive edge-based on-line Steiner algorithm. IEEE Journal of Selected Areas in Communications, 15:382--397, 1995.

Digital Library

[6]

M. W. Bern and P. E. Plassmann. The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett., 32(4):171--176, 1989.

Digital Library

[7]

V. Bilò, M. Flammini, and L. Moscardelli. The price of stability for undirected broadcast network design with fair cost allocation is constant. In FOCS, pages 638--647. IEEE Computer Society, 2013.

Digital Library

[8]

G. Borradaile, P. N. Klein, and C. Mathieu. An O(n log n) approximation scheme for Steiner tree in planar graphs. ACM Transactions on Algorithms, 5(3), 2009.

Digital Library

[9]

J. Byrka, F. Grandoni, T. Rothvoss, and L. Sanità. Steiner tree approximation via iterative randomized rounding. J. ACM, 60(1):6:1--6:33, Feb. 2013.

Digital Library

[10]

T. M. Chan. Dynamic subgraph connectivity with geometric applications. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC '02, pages 7--13, New York, NY, USA, 2002. ACM.

Digital Library

[11]

T. M. Chan, M. Patrascu, and L. Roditty. Dynamic connectivity: Connecting to networks and geometry. SIAM Journal on Computing, 40(2):333--349, 2011. See also FOCS'08, arXiv:0808.1128.

Digital Library

[12]

S. Chechik. Improved distance oracles and spanners for vertex-labeled graphs. In L. Epstein and P. Ferragina, editors, ESA, volume 7501 of Lecture Notes in Computer Science, pages 325--336. Springer, 2012.

Digital Library

[13]

X. Cheng, Y. Li, D.-Z. Du, and H. Ngo. Steiner trees in industry. In D.-Z. Du and P. Pardalos, editors, Handbook of Combinatorial Optimization, pages 193--216. Springer US, 2005.

[14]

F. Chung. Graph theory in the information age. Notices of the American Mathematrical Society, 57(06):726.

[15]

M. Cygan, L. Kowalik, M. Mucha, M. Pilipczuk, and P. Sankowski. Fast approximation in subspaces by doubling metric decomposition. In ESA (1), pages 72--83, 2010.

Digital Library

[16]

S. E. Deering and D. R. Cheriton. Multicast routing in datagram internetworks and extended lans. ACM Trans. Comput. Syst., 8(2):85--110, May 1990.

Digital Library

[17]

C. Demetrescu, D. Eppstein, Z. Galil, and G. F. Italiano. Algorithms and theory of computation handbook. chapter Dynamic Graph Algorithms, pages 9--9. Chapman & Hall/CRC, 2010.

Digital Library

[18]

N. Garg, A. Gupta, S. Leonardi, and P. Sankowski. Stochastic analyses for online combinatorial optimization problems. In SODA, pages 942--951, 2008.

Digital Library

[19]

A. Gu, A. Gupta, and A. Kumar. The power of deferral: maintaining a constant-competitive Steiner tree online. In STOC, pages 525--534, 2013.

Digital Library

[20]

A. Gupta and A. Kumar. Online Steiner tree with deletions. In C. Chekuri, editor, SODA, pages 455--467. SIAM, 2014.

Digital Library

[21]

A. Gupta, M. Pál, R. Ravi, and A. Sinha. Boosted sampling: approximation algorithms for stochastic optimization. In STOC, pages 417--426, 2004.

Digital Library

[22]

D. Hermelin, A. Levy, O. Weimann, and R. Yuster. Distance oracles for vertex-labeled graphs. In ICALP, pages 490--501, 2011.

Digital Library

[23]

J. Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723--760, 2001.

Digital Library

[24]

S.-P. Hong, H. Lee, and B. H. Park. An efficient multicast routing algorithm for delay-sensitive applications with dynamic membership. In INFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 3, pages 1433--1440 vol.3, Mar 1998.

[25]

M. Imase and B. M. Waxman. Dynamic Steiner tree problem. SIAM J. Discrete Math., 4(3):369--384, 1991.

Digital Library

[26]

M. Li, C. Ma, and L. Ning. (1+ε)-distance oracles for vertex-labeled planar graphs. In Theory and Applications of Models of Computation, volume 7876 of Lecture Notes in Computer Science, pages 42--51. 2013.

[27]

N. Megow, M. Skutella, J. Verschae, and A. Wiese. The power of recourse for online MST and TSP. In ICALP, pages 689--700. 2012.

Digital Library

[28]

K. Mehlhorn. A faster approximation algorithm for the Steiner problem in graphs. Inf. Process. Lett., 27(3):125--128, 1988.

Digital Library

[29]

J. S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput, 28:402--408, 1996.

Digital Library

[30]

S. Raghavan, G. Manimaran, C. Siva, and R. Murthy. A rearrangeable algorithm for the construction of delay-constrained dynamic multicast trees. IEEE/ACM Transactions on Networking, 7:514--529, 1999.

Digital Library

[31]

G. Robins and A. Zelikovsky. Tighter bounds for graph Steiner tree approximation. SIAM J. Discret. Math., 19(1):122--134, May 2005.

Digital Library

[32]

R. E. Tarjan and U. Vishkin. Finding biconnected componemts and computing tree functions in logarithmic parallel time. In Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984, SFCS '84, pages 12--20, Washington, DC, USA, 1984. IEEE Computer Society.

Digital Library

[33]

M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51:993--1024, 2004.

Digital Library

[34]

M. Thorup and U. Zwick. Approximate distance oracles. J. ACM, 52(1):1--24, 2005.

Digital Library

Cited By

Mellou KMolinaro MZhou R(2024)The Power of Migrations in Dynamic Bin PackingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004358:3(1-28)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1145/3700435
Chan TGoranci GJiang SWang BXue Q(2024)Fully Dynamic Algorithms for Euclidean Steiner TreeWALCOM: Algorithms and Computation10.1007/978-981-97-0566-5_6(62-75)Online publication date: 29-Feb-2024
https://doi.org/10.1007/978-981-97-0566-5_6
Bhattacharya SBuchbinder NLevin RSaranurak T(2023)Chasing Positive Bodies2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00103(1694-1714)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00103
Show More Cited By

Index Terms

The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Fully Dynamic Algorithm for Steiner Tree using Dynamic Distance Oracle
ICDCN '22: Proceedings of the 23rd International Conference on Distributed Computing and Networking

In this paper, we propose a fully dynamic algorithm for the Steiner tree problem in a planar graph. We consider a planar edge-weighted undirected graph with positive real edge weights and a set of updates including edge insertion/deletion. The goal is ...
The power-pSteiner tree problem

This paper introduces the power-p Steiner tree problem, which is to find a geometric Steiner tree that minimizes the sum of the edge lengths each raised to the p power. A number of results are presented on computing optimal and approximate power-p ...
Fully dynamic biconnectivity and transitive closure
FOCS '95: Proceedings of the 36th Annual Symposium on Foundations of Computer Science

This paper presents an algorithm for the fully dynamic biconnectivity problem whose running time is exponentially faster than all previously known solutions. It is the first dynamic algorithm that answers biconnectivity queries in time O(log/sup 2/n) in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

June 2015

916 pages

ISBN:9781450335362

DOI:10.1145/2746539

General Chair:
Rocco Servedio
Columbia University
,
Program Chair:
Ronitt Rubinfeld
MIT and Tel Aviv University

Copyright © 2015 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 the author(s) 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].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '15

Sponsor:

SIGACT

STOC '15: Symposium on Theory of Computing

June 14 - 17, 2015

Oregon, Portland, USA

Acceptance Rates

STOC '15 Paper Acceptance Rate 93 of 347 submissions, 27%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
447
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)1

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mellou KMolinaro MZhou R(2024)The Power of Migrations in Dynamic Bin PackingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004358:3(1-28)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1145/3700435
Chan TGoranci GJiang SWang BXue Q(2024)Fully Dynamic Algorithms for Euclidean Steiner TreeWALCOM: Algorithms and Computation10.1007/978-981-97-0566-5_6(62-75)Online publication date: 29-Feb-2024
https://doi.org/10.1007/978-981-97-0566-5_6
Bhattacharya SBuchbinder NLevin RSaranurak T(2023)Chasing Positive Bodies2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00103(1694-1714)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00103
Raikwar HKarmakar S(2023)An Incremental Algorithm for (2-ε)-Approximate Steiner Tree Requiring O(n) Update Time2023 Eleventh International Symposium on Computing and Networking (CANDAR)10.1109/CANDAR60563.2023.00030(168-174)Online publication date: 28-Nov-2023
https://doi.org/10.1109/CANDAR60563.2023.00030
Roditty LTov R(2023)Approximate distance oracles with improved stretch for sparse graphsTheoretical Computer Science10.1016/j.tcs.2022.11.016943(89-101)Online publication date: Jan-2023
https://doi.org/10.1016/j.tcs.2022.11.016
Raikwar HKarmakar S(2022)Fully Dynamic Algorithm for the Steiner Tree Problem in Planar Graphs2022 Tenth International Symposium on Computing and Networking Workshops (CANDARW)10.1109/CANDARW57323.2022.00064(416-420)Online publication date: Nov-2022
https://doi.org/10.1109/CANDARW57323.2022.00064
Fichtenberger HLattanzi SNorouzi-Fard ASvensson OMarx D(2021)Consistent k-clustering for general metricsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458222(2660-2678)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458222
Bergamaschi THenzinger MGutenberg MWilliams VWein NMarx D(2021)New techniques and fine-grained hardness for dynamic near-additive spannersProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458174(1836-1855)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458174
Kociumaka TSeddighin SKhuller SVassilevska Williams V(2021)Improved dynamic algorithms for longest increasing subsequenceProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451026(640-653)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451026
Roditty LTov R(2021)Approximate Distance Oracles with Improved Stretch for Sparse GraphsComputing and Combinatorics10.1007/978-3-030-89543-3_8(89-100)Online publication date: 20-Oct-2021
https://doi.org/10.1007/978-3-030-89543-3_8
Show More Cited By

View Options

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