Projects per year
Abstract
In the kedgeconnected spanning subgraph (kECSS) problem, our goal is to compute a minimumcost subnetwork that is resilient against up to k link failures: Given an nnode medge graph with a cost function on the edges, our goal is to compute a minimumcost kedgeconnected spanning subgraph. This NPhard 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 polynomialtime algorithms for the whole class of SNDP, even for a special case of 2ECSS. The fastest 2approximation algorithm is however rather slow, taking O(mnk) time [Khuller, Vishkin, STOC'92]. A faster time complexity of O(n^{2}) 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 language  English 

Title of host publication  49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 
Editors  Mikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff 
Publisher  Schloss DagstuhlLeibnizZentrum für Informatik 
Pages  120 
Number of pages  20 
ISBN (Electronic)  9783959772358 
DOIs  
Publication status  Published  1 Jul 2022 
MoE publication type  A4 Article in a conference publication 
Event  International Colloquium on Automata, Languages and Programming  Paris, France Duration: 4 Jul 2022 → 8 Jul 2022 Conference number: 49 https://icalp2022.irif.fr/ 
Publication series
Name  Leibniz International Proceedings in Informatics, LIPIcs 

Publisher  Schloss DagstuhlLeibnizZentrum für Informatik 
Volume  229 
ISSN (Electronic)  18688969 
Conference
Conference  International Colloquium on Automata, Languages and Programming 

Abbreviated title  ICALP 
Country/Territory  France 
City  Paris 
Period  04/07/2022 → 08/07/2022 
Internet address 
Keywords
 Approximation Algorithms
 Data Structures
Fingerprint
Dive into the research topics of 'Approximating kEdgeConnected Spanning Subgraphs via a NearLinear Time LP Solver'. Together they form a unique fingerprint.
ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P., Jindal, G., Gadekar, A., Orgo, L., Jiamjitrak, W., Khodamoradi, K., Franck, M., Spoerhase, J. & Yingchareonthawornchai, S.
01/02/2018 → 31/01/2024
Project: EU: ERC grants

Combinatorics of Graph Packing and Online Binary Search Trees
Chalermsook, P., Jiamjitrak, W., Gadekar, A., Franck, M., Obscura Acosta, N. & Uniyal, S.
01/09/2017 → 31/08/2022
Project: Academy of Finland: Other research funding