An improved approximation algorithm for the minimum k-edge connected multi-subgraph problem
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang
2022年份
6被引次数
5顶会引用
摘要
We give a randomized 1 + 5.06 √ k -approximation algorithm for the minimum k-edge connected spanning multi-subgraph problem, k-ECSM.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式，引用它的顶会 Paper 也一样。你提问，回答直接引用原文。
引用它的顶会 Paper5
- A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSPAnna R. Karlin, Nathan Klein, Shayan Oveis GharanFOCS 2022 · 被引用 13 次
- Almost Tight Additive Guarantees for k-Edge-ConnectivityNikhil Kumar, Chaitanya SwamyFOCS 2025 · 被引用 4 次
- Ghost Value Augmentation for k-Edge-ConnectivityD. Ellis Hershkowitz, Nathan Klein, Rico ZenklusenSTOC 2024 · 被引用 1 次
- Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic DepthZhuan Khye Koh, Omri Weinstein, Sorrachai YingchareonthawornchaiSTOC 2025 · 被引用 1 次
- Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic IndependenceNima Anari, Yang P. Liu, Thuy-Duong VuongFOCS 2022 · 被引用 1 次
它引用的顶会 Paper5
- A (slightly) improved approximation algorithm for metric TSPAnna R. Karlin, Nathan Klein, Shayan Oveis GharanSTOC 2021 · 被引用 114 次
- Bridging the gap between tree and connectivity augmentation: unified and stronger approachesFederica Cecchetto, Vera Traub, Rico ZenklusenSTOC 2021 · 被引用 22 次
- A Better-Than-2 Approximation for Weighted Tree AugmentationVera Traub, Rico ZenklusenFOCS 2021 · 被引用 20 次
- Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner treeJaroslaw Byrka, Fabrizio Grandoni, Afrouz Jabal AmeliSTOC 2020 · 被引用 19 次
- A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSPAnna R. Karlin, Nathan Klein, Shayan Oveis GharanFOCS 2022 · 被引用 13 次
相关 Paper
- A Nearly Time-Optimal Distributed Approximation of Minimum Cost k-Edge-Connected Spanning SubgraphMichal Dory, Mohsen GhaffariSODA 2023 · 被引用 1 次
- A 5/4-Approximation for Two-Edge ConnectivityMiguel Bosch-Calvo, Mohit Garg, Fabrizio Grandoni, Felix Hommelsheim 等STOC 2025 · 被引用 9 次
- 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 次
- Edge connectivity augmentation in near-linear timeRuoxu Cen, Jason Li, Debmalya PanigrahiSTOC 2022 · 被引用 2 次
