Document Open Access Logo

Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering

Authors Sina Dehghani, Soheil Ehsani, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Harald Räcke, Saeed Seddighin

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.42.pdf
  • Filesize: 0.7 MB
  • 14 pages

Document Identifiers

Author Details

Sina Dehghani
Soheil Ehsani
Mohammad Taghi Hajiaghayi
Vahid Liaghat
Harald Räcke
Saeed Seddighin

Cite As Get BibTex

Sina Dehghani, Soheil Ehsani, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Harald Räcke, and Saeed Seddighin. Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.42

Abstract

We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest (EW-DB-SF) problem and its generalized variant. We obtain our result by demonstrating a new generic approach for solving mixed packing/covering integer programs in the online paradigm. In EW-DB-SF, we are given an edge-weighted graph with a degree bound for every vertex. Given a root vertex in advance, we receive a sequence of terminal vertices in an online manner. Upon the arrival of a terminal, we need to augment our solution subgraph to connect the new terminal to the root. The goal is to minimize the total weight of the solution while respecting the degree bounds on the vertices. In the offline setting, edge-weighted degree-bounded Steiner tree (EW-DB-ST) and its many variations have been extensively studied since early eighties. Unfortunately, the recent advancements in the online network design problems are inherently difficult to adapt for degree-bounded problems. In particular, it is not known whether the fractional solution obtained by standard primal-dual techniques for mixed packing/covering LPs can be rounded online. In contrast, in this paper we obtain our result by using structural properties of the optimal solution, and reducing the EW-DB-SF problem to an exponential-size mixed packing/covering integer program in which every variable appears only once in covering constraints. We then design a generic integral algorithm for solving this restricted family of IPs.

As mentioned above, we demonstrate a new technique for solving mixed packing/covering integer programs. Define the covering frequency k of a program as the maximum number of covering constraints in which a variable can participate. Let m denote the number of packing constraints. We design an online deterministic integral algorithm with competitive ratio of O(k*log(m)) for the mixed packing/covering integer programs. We prove the tightness of our result by providing a matching lower bound for any randomized algorithm. We note that our solution solely depends on m and k. Indeed, there can be exponentially many variables. Furthermore, our algorithm directly provides an integral solution, even if the integrality gap of the program is unbounded. We believe this technique can be used as an interesting alternative for the standard primal-dual techniques in solving online problems.

Subject Classification

Keywords
  • Online
  • Steiner Tree
  • Approximation
  • Competitive ratio

Metrics

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

References

  1. Ajit Agrawal, Philip Nathan Klein, and R Ravi. How tough is the minimum-degree steiner tree?: A new approximate min-max equality. Technical Report CS-91-49, Brown University, 1991. Google Scholar
  2. 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
  3. James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, and Orli Waarts. On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the ACM (JACM), 44(3):486-504, 1997. Google Scholar
  4. Baruch Awerbuch, Yossi Azar, and Yair Bartal. On-line generalized steiner problem. In Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, pages 68-74, 1996. Google Scholar
  5. Yossi Azar, Umang Bhaskar, Lisa Fleischer, and Debmalya Panigrahi. Online mixed packing and covering. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 85-100. SIAM, 2013. Google Scholar
  6. Fred Bauer and Anujan Varma. Degree-constrained multicasting in point-to-point networks. In INFOCOM'95. Fourteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Bringing Information to People. Proceedings. IEEE, pages 369-376. IEEE, 1995. Google Scholar
  7. 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, 1997. Google Scholar
  8. Niv Buchbinder and Joseph Naor. The design of competitive online algorithms via a primal: dual approach. Foundations and Trendsregistered in Theoretical Computer Science, 3(2-3):93-263, 2009. Google Scholar
  9. Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, and Debmalya Panigrahi. Online buy-at-bulk network design. In FOCS, 2015. Google Scholar
  10. Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, and Kunal Talwar. A push-relabel algorithm for approximating degree bounded msts. In Proceedings of the 33rd international conference on Automata, Languages and Programming-Volume Part I, pages 191-201. Springer-Verlag, 2006. Google Scholar
  11. Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, and Kunal Talwar. What would edmonds do? augmenting paths and witnesses for degree-bounded msts. Algorithmica, 55(1):157-189, 2009. Google Scholar
  12. Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, and Vahid Liaghat. Online degree-bounded steiner network design. In SODA, 2016. URL: http://web.stanford.edu/~vliaghat/uploads/notes.pdf.
  13. Alina Ene and Ali Vakilian. Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements. STOC, 2014. Google Scholar
  14. Takuro Fukunaga and R Ravi. Iterative rounding approximation algorithms for degree-bounded node-connectivity network design. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 263-272. IEEE, 2012. Google Scholar
  15. Martin Fürer and Balaji Raghavachari. An NC approximation algorithm for the minimum degree spanning tree problem. In Allerton Conf. on Communication, Control and Computing, pages 274-281, 1990. Google Scholar
  16. Martin Fürer and Balaji Raghavachari. Approximating the minimum-degree steiner tree to within one of optimal. Journal of Algorithms, 17(3):409-423, 1994. Google Scholar
  17. Michel X Goemans. Minimum bounded degree spanning trees. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on, pages 273-282. IEEE, 2006. Google Scholar
  18. Michel X Goemans. Minimum bounded degree spanning trees. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on, pages 273-282, 2006. Google Scholar
  19. Mohammad Taghi 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, 2013. Google Scholar
  20. 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
  21. Makoto Imase and Bernard M Waxman. Dynamic Steiner tree problem. SIAM Journal on Discrete Mathematics, 4(3):369-384, 1991. Google Scholar
  22. Rohit Khandekar, Guy Kortsarz, and Zeev Nutov. On some network design problems with degree constraints. Journal of Computer and System Sciences, 79(5):725-736, 2013. Google Scholar
  23. Philip N Klein, Radha Krishnan, Balaji Raghavachari, and R Ravi. Approximation algorithms for finding low-degree subgraphs. Networks, 44(3):203-215, 2004. Google Scholar
  24. Jochen Könemann and R Ravi. A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 537-546. ACM, 2000. Google Scholar
  25. Jochen Könemann and R Ravi. Primal-dual meets local search: approximating mst’s with nonuniform degree bounds. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 389-395. ACM, 2003. Google Scholar
  26. Lap Chi Lau, Joseph Naor, Mohammad R Salavatipour, and Mohit Singh. Survivable network design with degree or order constraints. SIAM Journal on Computing, 39(3):1062-1087, 2009. Google Scholar
  27. Lap Chi Lau and Mohit Singh. Additive approximation for bounded degree survivable network design. SIAM Journal on Computing, 42(6):2217-2242, 2013. Google Scholar
  28. Madhav V Marathe, R Ravi, Ravi Sundaram, SS Ravi, Daniel J Rosenkrantz, and Harry B Hunt III. Bicriteria network design problems. Journal of Algorithms, 28(1):142-171, 1998. Google Scholar
  29. R Garey Michael and S Johnson David. Computers and intractability: a guide to the theory of np-completeness. WH Freeman &Co., San Francisco, 1979. Google Scholar
  30. Joseph Naor, Debmalya Panigrahi, and Mohit Singh. Online node-weighted steiner tree and related problems. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 210-219, 2011. Google Scholar
  31. Zeev Nutov. Degree-constrained node-connectivity. In LATIN 2012: Theoretical Informatics, pages 582-593. Springer, 2012. Google Scholar
  32. Carlos AS Oliveira and Panos M Pardalos. A survey of combinatorial optimization problems in multicast routing. Computers &Operations Research, 32(8):1953-1981, 2005. Google Scholar
  33. 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
  34. Balaji Raghavachari. Algorithms for finding low degree structures. In Approximation algorithms for NP-hard problems, pages 266-295. PWS Publishing Co., 1996. Google Scholar
  35. R Ravi, Madhav V Marathe, SS Ravi, Daniel J Rosenkrantz, and Harry B Hunt III. Approximation algorithms for degree-constrained minimum-cost network-design problems. Algorithmica, 31(1):58-78, 2001. Google Scholar
  36. R Ravi and Mohit Singh. Delegate and conquer: An lp-based approximation algorithm for minimum degree msts. In Automata, Languages and Programming, pages 169-180. Springer, 2006. Google Scholar
  37. Mohit Singh and Lap Chi Lau. Approximating minimum bounded degree spanning trees to within one of optimal. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 661-670, 2007. Google Scholar
  38. Stefan Voß. Problems with generalized steiner problems. Algorithmica, 7(1):333-335, 1992. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact