An improved approximation algorithm for the minimum \(k\)-edge connected multi-subgraph problem. (English) Zbl 07774442
Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 1612-1620 (2022).
MSC:
| 68Qxx | Theory of computing |
Keywords:
approximation algorithms; edge connectivity; max entropy; network design; randomized rounding; strongly RayleighReferences:
| [1] | Arash Asadpour, Michel X. Goemans, Aleksander Mdry, Shayan Oveis Gharan, and Amin Saberi. 2017. An O (log n /log log n )-Approximation Algorithm for the Asymmetric Traveling Salesman Problem. Operations Research, 65, 4 (2017). · Zbl 1380.90229 |
| [2] | Julius Borcea, Petter Brändén, and Thomas M. Liggett. 2009. Negative dependence and the geometry of polynomials. Journal of the American Mathematical Society, 22, 2 (2009), 521-567. · Zbl 1206.62096 |
| [3] | Sylvia Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, and Lu Wang. 2020. A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case. In APPROX/RANDOM, Jarosł aw Byrka and Raghu Meka (Eds.). 176, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 61:1-61:12. · Zbl 07572599 |
| [4] | Sylvia Boyd, Yao Fu, and Yu Sun. 2016. A 5/4-approximation for subcubic 2EC using circulations and obliged edges. Discrete Applied Mathematics, 209 (2016), 48-58. · Zbl 1339.05260 |
| [5] | Jaroslaw Byrka, Fabrizio Grandoni, and Afrouz Jabal Ameli. 2020. Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. In STOC, Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy (Eds.). ACM, 815-825. · Zbl 07298290 |
| [6] | Robert Carr and R. Ravi. 1998. A New Bound for the 2-Edge Connected Subgraph Problem. In IPCO, Robert E. Bixby, E. Andrew Boyd, and Roger Z. Ríos-Mercado (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 112-125. · Zbl 0907.90268 |
| [7] | Federica Cecchetto, Vera Traub, and Rico Zenklusen. 2021. Bridging the gap between tree and connectivity augmentation: unified and stronger approaches. In STOC, Samir Khuller and Virginia Vassilevska Williams (Eds.). ACM, 370-383. · Zbl 07765178 |
| [8] | Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. 2010. Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures. In FOCS. 575-584. |
| [9] | J. Cheriyan and R. Thurimella. 2000. Approximating minimum- size k-connected spanning subgraphs via matching. SIAM J Comput, 30 (2000), 528-560. · Zbl 1049.90104 |
| [10] | Jack Edmonds. 1970. Submodular functions, matroids and certain polyhedra. In Combinatorial Structures and Their Applications. Gordon and Breach, New York, NY, USA. 69-87. · Zbl 0268.05019 |
| [11] | Samuel Fiorini, Martin Groß, Jochen Könemann, and Laura Sanità. 2018. Approximating Weighted Tree Augmentation via Chvátal-Gomory Cuts. In SODA. 817-831. · Zbl 1403.68347 |
| [12] | G. N. Fredrickson and Joseph F. JáJá. 1981. Approximation Algorithms for Several Graph Augmentation Problems. SIAM J. Comput., 10, 2 (1981), 270-283. · Zbl 0461.05040 |
| [13] | G. N. Fredrickson and Joseph F. JáJá. 1982. On the relationship between the biconnectivity augmentation and traveling salesman problem. Theoretical Computer Science, 19 (1982), 189 - 201. · Zbl 0486.90082 |
| [14] | H. Gabow. 2005. An improved analysis for approximating the smallest k-edge connected spanning subgraph of a multi-graph. SIAM J Disc Math, 19 (2005), 1-18. · Zbl 1082.05087 |
| [15] | H. Gabow and S. Gallagher. 2008. Iterated rounding algorithms for the smallest k-edge connected spanning subgraph. SIAM J. Comput., 41 (2008), 61-103. · Zbl 1243.68225 |
| [16] | Harold N. Gabow, Michel X. Goemans, Éva Tardos, and David P. Williamson. 2009. Approximating the smallest k-edge connected spanning subgraph by LP-rounding. Networks, 53, 4 (2009), 345-357. · Zbl 1205.05125 |
| [17] | Michel X. Goemans and Dimitris Bertsimas. 1993. Survivable networks, linear programming relaxations and the parsimonious property. Math. Program., 60 (1993), 145-166. · Zbl 0790.90072 |
| [18] | Wassily Hoeffding. 1956. On the distribution of the number of successes in independent trials. Annals of Mathematical statistics, 27, 3 (1956), 713-721. · Zbl 0073.13902 |
| [19] | D. Karger. 1999. Random sampling in cut, flow, and network design problems. Math OR, 24 (1999), 383-413. · Zbl 0977.90074 |
| [20] | Anna Karlin, Nathan Klein, and Shayan Oveis Gharan. 2021. A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. arxiv:2105.10043. · Zbl 07298228 |
| [21] | Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. 2021. A (Slightly) Improved Approximation Algorithm for Metric TSP. In STOC. ACM. · Zbl 07298228 |
| [22] | S. Khuller and B. Raghavachari. 1996. Improved approximation algorithms for uniform connectivity problems. J Algorithms, 21 (1996), 434-450. · Zbl 0857.68052 |
| [23] | Bundit Laekhanukit, Shayan Oveis Gharan, and Mohit Singh. 2012. A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem. In ICALP, Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer (Eds.) (Lecture Notes in Computer Science, Vol. 7391). Springer, 606-616. · Zbl 1272.68461 |
| [24] | Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. 2011. A Randomized Rounding Approach to the Traveling Salesman Problem. In FOCS. IEEE Computer Society, 550-559. · Zbl 1292.68171 |
| [25] | Jim Pitman. 1997. Probabilistic bounds on the coefficients of polynomials with only real zeros. Journal of Combinatorial Theory, Series A, 77, 2 (1997), 279-303. · Zbl 0866.60016 |
| [26] | David Pritchard. 2011. k-Edge-Connectivity: Approximation and LP Relaxation. In Approximation and Online Algorithms, Klaus Jansen and Roberto Solis-Oba (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 225-236. · Zbl 1314.68402 |
| [27] | András Sebö and Jens Vygen. 2014. Shorter tours by nicer ears: 7/5-Approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica, 34, 5 (2014), 597-629. · Zbl 1340.90201 |
| [28] | Vera Traub and Rico Zenklusen. 2021. A Better-Than-2 Approximation for Weighted Tree Augmentation. to appear |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
