Greedy Algorithms for Online Survivable Network Design

Authors Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, Saeed Seddighin



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.152.pdf
  • Filesize: 463 kB
  • 14 pages

Document Identifiers

Author Details

Sina Dehghani
  • University of Maryland, College Park, MD 20742, USA
Soheil Ehsani
  • University of Maryland, College Park, MD 20742, USA
MohammadTaghi Hajiaghayi
  • University of Maryland, College Park, MD 20742, USA
Vahid Liaghat
  • Facebook, Building 25, 190 Jefferson Dr, Menlo Park, CA 94025, USA
Saeed Seddighin
  • University of Maryland, College Park, MD 20742, USA

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 152:1-152:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.152

Abstract

In an instance of the network design problem, we are given a graph G=(V,E), an edge-cost function c:E -> R^{>= 0}, and a connectivity criterion. The goal is to find a minimum-cost subgraph H of G that meets the connectivity requirements. An important family of this class is the survivable network design problem (SNDP): given non-negative integers r_{u v} for each pair u,v in V, the solution subgraph H should contain r_{u v} edge-disjoint paths for each pair u and v. While this problem is known to admit good approximation algorithms in the offline case, the problem is much harder in the online setting. Gupta, Krishnaswamy, and Ravi [Gupta et al., 2012] (STOC'09) are the first to consider the online survivable network design problem. They demonstrate an algorithm with competitive ratio of O(k log^3 n), where k=max_{u,v} r_{u v}. Note that the competitive ratio of the algorithm by Gupta et al. grows linearly in k. Since then, an important open problem in the online community [Naor et al., 2011; Gupta et al., 2012] is whether the linear dependence on k can be reduced to a logarithmic dependency. Consider an online greedy algorithm that connects every demand by adding a minimum cost set of edges to H. Surprisingly, we show that this greedy algorithm significantly improves the competitive ratio when a congestion of 2 is allowed on the edges or when the model is stochastic. While our algorithm is fairly simple, our analysis requires a deep understanding of k-connected graphs. In particular, we prove that the greedy algorithm is O(log^2 n log k)-competitive if one satisfies every demand between u and v by r_{uv}/2 edge-disjoint paths. The spirit of our result is similar to the work of Chuzhoy and Li [Chuzhoy and Li, 2012] (FOCS'12), in which the authors give a polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. Moreover, we study the greedy algorithm in the online stochastic setting. We consider the i.i.d. model, where each online demand is drawn from a single probability distribution, the unknown i.i.d. model, where every demand is drawn from a single but unknown probability distribution, and the prophet model in which online demands are drawn from (possibly) different probability distributions. Through a different analysis, we prove that a similar greedy algorithm is constant competitive for the i.i.d. and the prophet models. Also, the greedy algorithm is O(log n)-competitive for the unknown i.i.d. model, which is almost tight due to the lower bound of [Garg et al., 2008] for single connectivity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • survivable network design
  • online
  • greedy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem. SIAM Journal on Computing, 39(2):361-370, 2009. Google Scholar
  2. Baruch Awerbuch, Yossi Azar, and Yair Bartal. On-line generalized steiner problem. Theoretical Computer Science, 324(2):313-324, 2004. Google Scholar
  3. Piotr Berman and Chris Coulston. On-line algorithms for steiner tree problems. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 344-353. ACM, 1997. Google Scholar
  4. Robert Carr and Santosh Vempala. Randomized metarounding. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 58-62. ACM, 2000. Google Scholar
  5. Chandra Chekuri and Nitish Korula. A graph reduction step preserving element-connectivity and applications. In International Colloquium on Automata, Languages, and Programming, pages 254-265. Springer, 2009. Google Scholar
  6. Joseph Cheriyan and Mohammad R Salavatipour. Hardness and approximation results for packing steiner trees. Algorithmica, 45(1):21-43, 2006. Google Scholar
  7. Julia Chuzhoy and Shi Li. A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 233-242. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.54.
  8. Matt DeVos, Jessica McDonald, and Irene Pivotto. Packing steiner trees. arXiv preprint arXiv:1307.7621, 2013. Google Scholar
  9. Naveen Garg, Anupam Gupta, Stefano Leonardi, and Piotr Sankowski. Stochastic analyses for online combinatorial optimization problems. In SODA, pages 942-951. Society for Industrial and Applied Mathematics, 2008. Google Scholar
  10. Michel X Goemans, Andrew V Goldberg, Serge A Plotkin, David B Shmoys, Eva Tardos, and David P Williamson. Improved approximation algorithms for network design problems. In SODA, volume 94, pages 223-232, 1994. Google Scholar
  11. Michel X Goemans and David P Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24(2):296-317, 1995. Google Scholar
  12. Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, and Mohit Singh. Set covering with our eyes closed. In Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pages 347-356. IEEE, 2008. Google Scholar
  13. Anupam Gupta and Jochen Könemann. Approximation algorithms for network design: A survey. Surveys in Operations Research and Management Science, 16(1):3-20, 2011. Google Scholar
  14. Anupam Gupta, Ravishankar Krishnaswamy, and R Ravi. Online and stochastic survivable network design. SIAM Journal on Computing, 41(6):1649-1672, 2012. Google Scholar
  15. Mohammad T Hajiaghayi, Vahid Liaghat, and Debmalya Panigrahi. Online node-weighted steiner forest and extensions via disk paintings. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 558-567. IEEE, 2013. Google Scholar
  16. MohammadTaghi Hajiaghayi, Vahid Liaghat, and Debmalya Panigrahi. Near-optimal online algorithms for prize-collecting steiner problems. In Automata, Languages, and Programming, pages 576-587. Springer, 2014. Google Scholar
  17. Makoto Imase and Bernard M Waxman. Dynamic steiner tree problem. SIAM Journal on Discrete Mathematics, 4(3):369-384, 1991. Google Scholar
  18. Kamal Jain. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica, 21(1):39-60, 2001. Google Scholar
  19. Kamal Jain, Mohammad Mahdian, and Mohammad R Salavatipour. Packing steiner trees. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 266-274. Society for Industrial and Applied Mathematics, 2003. Google Scholar
  20. Matthias Kriesell. Edge-disjoint trees containing some given vertices in a graph. Journal of Combinatorial Theory, Series B, 88(1):53-65, 2003. Google Scholar
  21. Lap Chi Lau. An approximate max-steiner-tree-packing min-steiner-cut theorem. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 61-70. IEEE, 2004. Google Scholar
  22. Joseph Naor, Debmalya Panigrahi, and Monika Singh. Online node-weighted steiner tree and related problems. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 210-219. IEEE, 2011. Google Scholar
  23. CSJA Nash-Williams. Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society, 1(1):445-450, 1961. Google Scholar
  24. Louis Petingi and J Rodriguez. Bounds on the maximum number of edge-disjoint steiner trees of a graph. Congressus Numerantium, pages 43-52, 2000. Google Scholar
  25. Jiawei Qian and David P Williamson. An o (logn)-competitive algorithm for online constrained forest problems. In Automata, Languages and Programming, pages 37-48. Springer, 2011. Google Scholar
  26. R Ravi and Philip Klein. When cycles collapse: A general approximation technique for constrained two-connectivity problems. In 3rd Conference on Integer Programming and Combinatorial Optimization, pages 39-56, 1993. Google Scholar
  27. David P Williamson, Michel X Goemans, Milena Mihail, and Vijay V Vazirani. A primal-dual approximation algorithm for generalized steiner network problems. Combinatorica, 15(3):435-454, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail