Open access
Date
2024-06Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
We give a poly-time algorithm for the k-edge-connected spanning subgraph (k-ECSS) problem that returns a solution of cost no greater than the cheapest (k+10)-ECSS on the same graph. Our approach enhances the iterative relaxation framework with a new ingredient, which we call ghost values, that allows for high sparsity in intermediate problems. Our guarantees improve upon the best-known approximation factor of 2 for k-ECSS whenever the optimal value of (k+10)-ECSS is close to that of k-ECSS. This is a property that holds for the closely related problem k-edge-connected spanning multi-subgraph (k-ECSM), which is identical to k-ECSS except edges can be selected multiple times at the same cost. As a consequence, we obtain a 1+O(1/k)-approximation algorithm for k-ECSM, which resolves a conjecture of Pritchard and improves upon a recent 1+O(1/√k)-approximation algorithm of Karlin, Klein, Oveis Gharan, and Zhang. Moreover, we present a matching lower bound for k-ECSM, showing that our approximation ratio is tight up to the constant factor in O(1/k), unless P=NP. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000680547Publication status
publishedExternal links
Book title
STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of ComputingPages / Article No.
Publisher
Association for Computing MachineryEvent
Subject
Approximation Algorithms; Edge Connectivity; Network Design; Iterative RoundingOrganisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico
Funding
184622 - Toward Stronger Approximation Algorithms for Fundamental Network Design and Optimization Problems (SNF)
817750 - Fundamental Problems at the Interface of Combinatorial Optimization with Integer Programming and Online Optimization (EC)
Notes
Conference lecture held on June 28, 2024.More
Show all metadata
ETH Bibliography
yes
Altmetrics