LIPIcs.ICALP.2019.88.pdf
- Filesize: 0.66 MB
- 14 pages
Document
Tight Bounds for Online Weighted Tree Augmentation
Authors
Seeun William Umboh 
,
David P. Williamson
-
Part of:
Volume:
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-07-04
File
Document Identifiers
Author Details
Acknowledgements
This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing.
Cite AsGet BibTex
Joseph (Seffi) Naor, Seeun William Umboh, and David P. Williamson. Tight Bounds for Online Weighted Tree Augmentation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 88:1-88:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.88
https://doi.org/10.4230/LIPIcs.ICALP.2019.88
Abstract
The Weighted Tree Augmentation problem (WTAP) is a fundamental problem in network design. In this paper, we consider this problem in the online setting. We are given an n-vertex spanning tree T and an additional set L of edges (called links) with costs. Then, terminal pairs arrive one-by-one and our task is to maintain a low-cost subset of links F such that every terminal pair that has arrived so far is 2-edge-connected in T cup F. This online problem was first studied by Gupta, Krishnaswamy and Ravi (SICOMP 2012) who used it as a subroutine for the online survivable network design problem. They gave a deterministic O(log^2 n)-competitive algorithm and showed an Omega(log n) lower bound on the competitive ratio of randomized algorithms. The case when T is a path is also interesting: it is exactly the online interval set cover problem, which also captures as a special case the parking permit problem studied by Meyerson (FOCS 2005). The contribution of this paper is to give tight results for online weighted tree and path augmentation problems. The main result of this work is a deterministic O(log n)-competitive algorithm for online WTAP, which is tight up to constant factors.
Subject Classification
ACM Subject Classification
- Theory of computation → Online algorithms
Keywords
- Online algorithms
- competitive analysis
- tree augmentation
- network design
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The Online Set Cover Problem. SIAM J. Comput., 39(2):361-370, 2009. URL: http://dx.doi.org/10.1137/060661946.
-
Baruch Awerbuch, Yossi Azar, and Yair Bartal. On-line generalized Steiner problem. Theoretical Computer Science, 324:313-324, 2004.
-
Piotr Berman and Chris Coulston. On-Line Algorithms for Steiner Tree Problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 344-353, 1997.
- Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Saeed Seddighin. Greedy Algorithms for Online Survivable Network Design. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 152:1-152:14, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.152.
- Guy Even and Shakhar Smorodinsky. Hitting sets online and unique-max coloring. Discrete Applied Mathematics, 178:71-82, 2014. URL: http://dx.doi.org/10.1016/j.dam.2014.06.019.
- Greg N. Frederickson and Joseph JáJá. Approximation Algorithms for Several Graph Augmentation Problems. SIAM J. Comput., 10(2):270-283, 1981. URL: http://dx.doi.org/10.1137/0210019.
- Fabrizio Grandoni, Christos Kalaitzis, and Rico Zenklusen. Improved approximation for tree augmentation: saving by rewiring. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 632-645, 2018. URL: http://dx.doi.org/10.1145/3188745.3188898.
- Anupam Gupta, Ravishankar Krishnaswamy, and R. Ravi. Online and Stochastic Survivable Network Design. SIAM J. Comput., 41(6):1649-1672, 2012. URL: http://dx.doi.org/10.1137/09076725X.
-
MohammadTaghi Hajiaghayi, Vahid Liaghat, and Debmalya Panigrahi. Online Node-weighted Steiner Forest and Extensions via Disk Paintings. In Proceedings of the 54th Annual Symposium on Foundations of Computer Science, pages 558-567, 2013.
-
MohammadTaghi Hajiaghayi, Vahid Liaghat, and Debmalya Panigrahi. Near-Optimal Online Algorithms for Prize-Collecting Steiner Problems. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming, 41st International Colloquium, ICALP 2014, volume 8572 of Lecture Notes in Computer Science, pages 576-587. Springer, 2014.
-
Makoto Imase and Bernard M. Waxman. Dynamic Steiner Tree Problem. SIAM Journal on Discrete Mathematics, 4:369-384, 1991.
-
Adam Meyerson. The Parking Permit Problem. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 274-282, 2005.
- Joseph Naor, Debmalya Panigrahi, and Mohit Singh. Online Node-Weighted Steiner Tree and Related Problems. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 210-219, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.65.
-
Jiawei Qian, Seeun William Umboh, and David P. Williamson. Online Constrained Forest and Prize-Collecting Network Design. Algorithmica, 80(11):3335-3364, 2018.
- Daniel Dominic Sleator and Robert Endre Tarjan. A Data Structure for Dynamic Trees. J. Comput. Syst. Sci., 26(3):362-391, 1983. URL: http://dx.doi.org/10.1016/0022-0000(83)90006-5.
-
Seeun Umboh. Online Network Design Algorithms via Hierarchical Decompositions. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1373-1387, 2015.