Document Open Access Logo

Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions

Authors Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2023.15.pdf
  • Filesize: 0.85 MB
  • 19 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Approximation algorithms
  • Edge-connectivity of graphs
  • f-Connectivity problem
  • Flexible Graph Connectivity
  • Minimum cuts
  • Network design
  • Primal-dual method
  • Small cuts

Metrics

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

Abstract

We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Combinatorica 15(3):435-454, 1995). Williamson et al. prove an approximation ratio of two for connectivity augmentation problems where the connectivity requirements can be specified by uncrossable functions. They state: "Extending our algorithm to handle non-uncrossable functions remains a challenging open problem. The key feature of uncrossable functions is that there exists an optimal dual solution which is laminar... A larger open issue is to explore further the power of the primal-dual approach for obtaining approximation algorithms for other combinatorial optimization problems."
Our main result proves a 16-approximation ratio via the primal-dual method for a class of functions that generalizes the notion of an uncrossable function. There exist instances that can be handled by our methods where none of the optimal dual solutions have a laminar support.
We present applications of our main result to three network-design problems.  
1) A 16-approximation algorithm for augmenting the family of small cuts of a graph G. The previous best approximation ratio was O(log |V(G)|).
2) A 16⋅⌈k/u_min⌉-approximation algorithm for the Cap-k-ECSS problem which is as follows: Given an undirected graph G = (V,E) with edge costs c ∈ ℚ_{≥0}^E and edge capacities u ∈ ℤ_{≥0}^E, find a minimum cost subset of the edges F ⊆ E such that the capacity across any cut in (V,F) is at least k; u_min (respectively, u_max) denote the minimum (respectively, maximum) capacity of an edge in E, and w.l.o.g. u_max ≤ k. The previous best approximation ratio was min(O(log|V|), k, 2u_max).
3) A 20-approximation algorithm for the model of (p,2)-Flexible Graph Connectivity. The previous best approximation ratio was O(log|V(G)|), where G denotes the input graph.

Cite As Get BibTex

Ishan Bansal, Joseph Cheriyan, Logan Grout, and Sharat Ibrahimpur. Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.15

Author Details

Ishan Bansal
  • Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA
Joseph Cheriyan
  • Department of Combinatorics and Optimization, University of Waterloo, Canada
Logan Grout
  • Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA
Sharat Ibrahimpur
  • Department of Mathematics, London School of Economics and Political Science, UK

Funding

  • Bansal, Ishan: Partially supported by Office of Naval Research (ONR) Grant N00014-21-1-2575.
  • Cheriyan, Joseph: Supported in part by NSERC, RGPIN-2019-04197.
  • Ibrahimpur, Sharat: Received funding from the following sources: NSERC grant 327620-09 and an NSERC DAS Award, European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no. ScaleOpt–757481), and Dutch Research Council NWO Vidi Grant 016.Vidi.189.087.

Acknowledgements

We thank the anonymous reviewers and the ICALP PC for their comments. We are grateful to Cedric Koh and Madison Van Dyk for reading a preliminary version, and for their detailed comments and feedback.

References

  1. David Adjiashvili, Felix Hommelsheim, and Moritz Mühlenthaler. Flexible Graph Connectivity. Mathematical Programming, 192:409-441, 2022. URL: https://doi.org/10.1007/s10107-021-01664-9.
  2. Ajit Agrawal, Philip Klein, and R Ravi. When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks. SIAM Journal on Computing, 24(3):440-456, 1995. URL: https://doi.org/10.1137/S0097539792236237.
  3. Ishan Bansal, Joseph Cheriyan, Logan Grout, and Sharat Ibrahimpur. Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions. CoRR, abs/2209.11209v2, 2022. URL: https://arxiv.org/abs/2209.11209.
  4. András A. Benczúr and Michel X. Goemans. Deformable Polygon Representation and Near-Mincuts. In Building Bridges. Bolyai Society Mathematical Studies, pages 103-135. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-85221-6_3.
  5. Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, and Sharat Ibrahimpur. Approximation algorithms for flexible graph connectivity. Mathematical Programming, 2023. URL: https://doi.org/10.1007/s10107-023-01961-5.
  6. Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, and Nitish Korula. Approximability of Capacitated Network Design. Algorithmica, 72(2):493-514, 2015. URL: https://doi.org/10.1007/s00453-013-9862-4.
  7. Chandra Chekuri and Rhea Jain. Approximating Flexible Graph Connectivity via Räcke Tree based Rounding. CoRR, abs/2211.08324, 2022. URL: https://doi.org/10.48550/arXiv.2211.08324.
  8. Chandra Chekuri and Rhea Jain. Augmentation based Approximation Algorithms for Flexible Network Design. CoRR, abs/2209.12273, 2022. URL: https://doi.org/10.48550/arXiv.2209.12273.
  9. George B. Dantzig, Lester R. Ford Jr., and Delbert R. Fulkerson. A Primal-Dual Algorithm for Linear Programs. In Linear Inequalities and Related Systems, volume 38 of Annals of Mathematics Studies, pages 171-182. Princeton University Press, 1957. URL: https://doi.org/10.1515/9781400881987-008.
  10. Reinhard Diestel. Graph Theory. Graduate Texts in Mathematics. Springer, 2017. URL: https://doi.org/10.1007/978-3-662-53622-3.
  11. Lisa Fleischer, Kamal Jain, and David P. Williamson. Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. Journal of Computer and System Sciences, 72(5):838-867, 2006. URL: https://doi.org/10.1016/j.jcss.2005.05.006.
  12. András Frank. Connections in Combinatorial Optimization, volume 38 of Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, 2011. Google Scholar
  13. Greg N. Frederickson and Joseph F. JáJá. Approximation Algorithms for Several Graph Augmentation Problems. SIAM Journal on Computing, 10(2):270-283, 1981. URL: https://doi.org/10.1137/0210019.
  14. Harold N. Gabow and Suzanne Gallagher. Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph. SIAM Journal on Computing, 41(1):61-103, 2012. URL: https://doi.org/10.1137/080732572.
  15. Harold N. Gabow, Michel X. Goemans, Éva Tardos, and David P. Williamson. Approximating the Smallest k-Edge Connected Spanning Subgraph by LP-Rounding. Networks, 53(4):345-357, 2009. URL: https://doi.org/10.1002/net.20289.
  16. Harold N. Gabow, Michel X. Goemans, and David P. Williamson. An efficient approximation algorithm for the survivable network design problem. Mathematical Programming, 82:13-40, 1998. URL: https://doi.org/10.1007/BF01585864.
  17. Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, and David P. Williamson. Improved Approximation Algorithms for Network Design Problems. In Proceedings of the 5th Symposium on Discrete Algorithms, pages 223-232, 1994. Google Scholar
  18. Michel X. Goemans and David P. Williamson. A General Approximation Technique for Constrained Forest Problems. SIAM Journal on Computing, 24(2):296-317, 1995. URL: https://doi.org/10.1137/S0097539793242618.
  19. Michel X. Goemans and David P. Williamson. The Primal-Dual Method for Approximation Algorithms and Its Application to Network Design Problems. In Approximation Algorithms for NP-Hard Problems, chapter 4, pages 144-191. PWS Publishing Company, 1996. URL: https://math.mit.edu/~goemans/PAPERS/book-ch4.pdf.
  20. Kamal Jain. A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Combinatorica, 21(1):39-60, 2001. URL: https://doi.org/10.1007/s004930170004.
  21. David S. Johnson, Maria Minkoff, and Steven Phillips. The Prize Collecting Steiner Tree Problem: Theory and Practice. In David B. Shmoys, editor, Proceedings of the 11th Symposium on Discrete Algorithms, pages 760-769, 2000. URL: https://dl.acm.org/doi/10.5555/338219.338637.
  22. David R. Karger and Clifford Stein. A New Approach to the Minimum Cut Problem. Journal of the ACM, 43(4):601-640, 1996. URL: https://doi.org/10.1145/234533.234534.
  23. Samir Khuller and Ramakrishna Thurimella. Approximation Algorithms for Graph Augmentation. Journal of Algorithms, 14(2):214-225, 1993. URL: https://doi.org/10.1006/jagm.1993.1010.
  24. Samir Khuller and Uzi Vishkin. Biconnectivity Approximations and Graph Carvings. Journal of the ACM, 41(2):214-235, 1994. URL: https://doi.org/10.1145/174652.174654.
  25. Harold W. Kuhn. The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, 2(1-2):83-97, 1955. URL: https://doi.org/10.1002/nav.3800020109.
  26. Lap Chi Lau, R. Ravi, and Mohit Singh. Iterative Methods in Combinatorial Optimization. Cambridge Texts in Applied Mathematics. Cambridge University Press, 2011. URL: https://doi.org/10.1017/CBO9780511977152.
  27. Milena Mihail, David Shallcross, Nate Dean, and Marco Mostrel. A Commercial Application of Survivable Network Design: ITP/INPLANS CCS Network Topology Analyzer. In Proceedings of the 7th Symposium on Discrete Algorithms, pages 279-287, 1996. URL: https://dl.acm.org/doi/10.5555/313852.314074.
  28. Hiroshi Nagamochi, Kazuhiro Nishimura, and Toshihide Ibaraki. Computing All Small Cuts in an Undirected Network. SIAM Journal on Discrete Mathematics, 10(3):469-481, 1997. URL: https://doi.org/10.1137/S0895480194271323.
  29. Dalit Naor, Dan Gusfield, and Charles Martel. A Fast Algorithm for Optimally Increasing the Edge Connectivity. SIAM Journal on Computing, 26(4):1139-1165, 1997. URL: https://doi.org/10.1137/S0097539792234226.
  30. Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics. Springer, 2003. Google Scholar
  31. Vijay V. Vazirani. Approximation Algorithms. Springer, 2003. URL: https://doi.org/10.1007/978-3-662-04565-7.
  32. David P. Williamson and Michel X. Goemans. Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. INFORMS Journal on Computing, 8(1):29-40, 1996. URL: https://doi.org/10.1287/ijoc.8.1.29.
  33. 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. URL: https://doi.org/10.1007/BF01299747.
  34. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact