A $5/4$ Approximation for Two-Edge-Connectivity
<|reference_start|>A $5/4$ Approximation for Two-Edge-Connectivity: The $2$-Edge Connected Spanning Subgraph problem (2ECSS) is among the most basic survivable network design problems: given an undirected unweighted graph, find a subgraph with the minimum number of edges which is 2-edge-connected (i.e., it remains connected after the removal of any single edge). This NP-hard problem is well-studied in terms of approximation algorithms. The current-best approximation factor for 2ECSS is $1.3+\varepsilon$ for any constant $\varepsilon >0$ [Garg, Grandoni, Jabal-Ameli'23; Kobayashi,Noguchi'23]. In this paper we present a much simpler $9/7$ approximation algorithm, and a more complex $5/4$ one. Our algorithms are also faster: their running time is $n^{O(1)}$ instead of $n^{O(1/\varepsilon)}$.<|reference_end|>
@article{bosch-calvo2024a,
    title={A $5/4$ Approximation for Two-Edge-Connectivity},
    author={Miguel Bosch-Calvo, Fabrizio Grandoni, Afrouz Jabal Ameli},
    journal={arXiv preprint arXiv:2408.07019},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.07019},
    primaryClass={cs.DS math.CO}
}