2026-07-22T19:33:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16378 2024-03-06T10:57:19Z ddc:004 open_access

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver Chalermsook, Parinya Huang, Chien-Chung Nanongkai, Danupon Saranurak, Thatchaphol Sukprasert, Pattara Yingchareonthawornchai, Sorrachai Approximation Algorithms Data Structures 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(mn k) time [Khuller, Vishkin, STOC'92]. A faster time complexity of O(n²) 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/ε²) time (independent of k), which can be turned into a (2+ε) approximation algorithm that runs in time Õ(m/(ε²) + {k²n^{1.5}}/ε²) for (integral) kECSS; this improves the running time of the aforementioned results while keeping the approximation ratio arbitrarily close to a factor of two. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Parinya Chalermsook and Chien-Chung Huang and Danupon Nanongkai and Thatchaphol Saranurak and Pattara Sukprasert and Sorrachai Yingchareonthawornchai 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.37 urn:nbn:de:0030-drops-163785 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.37 eng https://creativecommons.org/licenses/by/4.0/legalcode