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

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

DOI

10.4230/LIPIcs.ICALP.2022.37

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

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202210196028

Collections

[article-cris] Perustieteiden korkeakoulu / SCI

Show all metadata

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

Access rights

URL

Journal Title

Journal ISSN

Volume Title

Authors

Date

Department

Major/Subject

Mcode

Degree programme

Language

Pages

Series