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

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

1 Sitaatiot (Scopus)
36 Lataukset (Pure)

Abstrakti

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.

AlkuperäiskieliEnglanti
Otsikko49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
ToimittajatMikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Sivut1-20
Sivumäärä20
ISBN (elektroninen)978-3-95977-235-8
DOI - pysyväislinkit
TilaJulkaistu - 1 heinäk. 2022
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaInternational Colloquium on Automata, Languages and Programming - Paris, Ranska
Kesto: 4 heinäk. 20228 heinäk. 2022
Konferenssinumero: 49
https://icalp2022.irif.fr/

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
KustantajaSchloss Dagstuhl-Leibniz-Zentrum für Informatik
Vuosikerta229
ISSN (elektroninen)1868-8969

Conference

ConferenceInternational Colloquium on Automata, Languages and Programming
LyhennettäICALP
Maa/AlueRanska
KaupunkiParis
Ajanjakso04/07/202208/07/2022
www-osoite

Sormenjälki

Sukella tutkimusaiheisiin 'Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä