Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
Date
2022-07-01
Major/Subject
Mcode
Degree programme
Language
en
Pages
20
1-20
Series
49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022, Leibniz International Proceedings in Informatics, LIPIcs, Volume 229
Abstract
In the k-edge-connected spanning subgraph (kECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to k link failures: Given an n-node m-edge graph with a cost function on the edges, our goal is to compute a minimum-cost k-edge-connected spanning subgraph. This NP-hard problem generalizes the minimum spanning tree problem and is the “uniform case” of a much broader class of survival network design problems (SNDP). A factor of two has remained the best approximation ratio for polynomial-time algorithms for the whole class of SNDP, even for a special case of 2ECSS. The fastest 2-approximation algorithm is however rather slow, taking O(mnk) time [Khuller, Vishkin, STOC'92]. A faster time complexity of O(n2) can be obtained, but with a higher approximation guarantee of (2k − 1) [Gabow, Goemans, Williamson, IPCO'93]. Our main contribution is an algorithm that (1 + ε)-approximates the optimal fractional solution in Õ(m/ε2) time (independent of k), which can be turned into a (2+ ε) approximation algorithm that runs in time (Equation presented) for (integral) kECSS; this improves the running time of the aforementioned results while keeping the approximation ratio arbitrarily close to a factor of two.
Description
| openaire: EC/H2020/759557/EU//ALGOCom | openaire: EC/H2020/715672/EU//DisDyn Funding Information: This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No 759557 & 715672. Nanongkai and Saranurak were also partially supported by the Swedish Research Council (Reg. No. 2015-04659.). Chalermsook was also supported by the Academy Research Fellowship (grant number 310415). Funding Information: Funding This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement No 759557 & 715672. Nanongkai and Saranurak were also partially supported by the Swedish Research Council (Reg. No. 2015-04659.). Chalermsook was also supported by the Academy Research Fellowship (grant number 310415). Publisher Copyright: © Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, and Sorrachai Yingchareonthawornchai; licensed under Creative Commons License CC-BY 4.0
Keywords
Approximation Algorithms, Data Structures
Other note
Citation
Chalermsook , P , Huang , C C , Nanongkai , D , Saranurak , T , Sukprasert , P & Yingchareonthawornchai , S 2022 , Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver . in M Bojanczyk , E Merelli & D P Woodruff (eds) , 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 . , 37 , Leibniz International Proceedings in Informatics, LIPIcs , vol. 229 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik , pp. 1-20 , International Colloquium on Automata, Languages and Programming , Paris , France , 04/07/2022 . https://doi.org/10.4230/LIPIcs.ICALP.2022.37