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

Parinya Chalermsook*, Chien Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, Sorrachai Yingchareonthawornchai

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2 Downloads (Pure)

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.

Original languageEnglish
Title of host publication49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
EditorsMikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff
PublisherSchloss Dagstuhl-Leibniz-Zentrum für Informatik
Pages1-20
Number of pages20
ISBN (Electronic)9783959772358
DOIs
Publication statusPublished - 1 Jul 2022
MoE publication typeA4 Article in a conference publication
EventInternational Colloquium on Automata, Languages and Programming - Paris, France
Duration: 4 Jul 20228 Jul 2022
Conference number: 49
https://icalp2022.irif.fr/

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl-Leibniz-Zentrum für Informatik
Volume229
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Colloquium on Automata, Languages and Programming
Abbreviated titleICALP
Country/TerritoryFrance
CityParis
Period04/07/202208/07/2022
Internet address

Keywords

  • Approximation Algorithms
  • Data Structures

Fingerprint

Dive into the research topics of 'Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver'. Together they form a unique fingerprint.

Cite this