An improved approximation algorithm for the minimum k-edge connected multi-subgraph problem
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang
2022Year
6Citations
5Top-tier citations
Abstract
We give a randomized 1 + 5.06 √ k -approximation algorithm for the minimum k-edge connected spanning multi-subgraph problem, k-ECSM.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Cited by top-tier papers5
- A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSPAnna R. Karlin, Nathan Klein, Shayan Oveis GharanFOCS 2022 · 13 citations
- Almost Tight Additive Guarantees for k-Edge-ConnectivityNikhil Kumar, Chaitanya SwamyFOCS 2025 · 4 citations
- Ghost Value Augmentation for k-Edge-ConnectivityD. Ellis Hershkowitz, Nathan Klein, Rico ZenklusenSTOC 2024 · 1 citation
- Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic DepthZhuan Khye Koh, Omri Weinstein, Sorrachai YingchareonthawornchaiSTOC 2025 · 1 citation
- Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic IndependenceNima Anari, Yang P. Liu, Thuy-Duong VuongFOCS 2022 · 1 citation
Builds on5
- A (slightly) improved approximation algorithm for metric TSPAnna R. Karlin, Nathan Klein, Shayan Oveis GharanSTOC 2021 · 114 citations
- Bridging the gap between tree and connectivity augmentation: unified and stronger approachesFederica Cecchetto, Vera Traub, Rico ZenklusenSTOC 2021 · 22 citations
- A Better-Than-2 Approximation for Weighted Tree AugmentationVera Traub, Rico ZenklusenFOCS 2021 · 20 citations
- Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner treeJaroslaw Byrka, Fabrizio Grandoni, Afrouz Jabal AmeliSTOC 2020 · 19 citations
- A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSPAnna R. Karlin, Nathan Klein, Shayan Oveis GharanFOCS 2022 · 13 citations
Related papers
- A Nearly Time-Optimal Distributed Approximation of Minimum Cost k-Edge-Connected Spanning SubgraphMichal Dory, Mohsen GhaffariSODA 2023 · 1 citation
- A 5/4-Approximation for Two-Edge ConnectivityMiguel Bosch-Calvo, Mohit Garg, Fabrizio Grandoni, Felix Hommelsheim et al.STOC 2025 · 9 citations
- Maximal k-Edge-Connected Subgraphs in Weighted Graphs via Local Random ContractionChaitanya Nalam, Thatchaphol SaranurakSODA 2023
- A Better-Than-5/4-Approximation for Two-Edge ConnectivityFelix Hommelsheim, Alexander Lindermayr, Zhenwei LiuSODA 2026 · 2 citations
- Edge connectivity augmentation in near-linear timeRuoxu Cen, Jason Li, Debmalya PanigrahiSTOC 2022 · 2 citations
