A Better-Than- 5 / 4 5/4 -Approximation for Two-Edge Connectivity
Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu · 2025
Read A Better-Than- 5 / 4 5/4 -Approximation for Two-Edge Connectivity by Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-19655.txt.
Introduction
A network that stays connected after any single cable cut is two-edge-connected, and builders want the cheapest such network. Felix Hommelsheim, Alexander Lindermayr, and Zhenwei Liu improve the best approximation guarantee for that spanning subgraph problem. The known best ratio, five quarters, came from a 2025 result and looked like a natural wall. Their algorithm slips just below it by a small constant.
The route starts from a triangle-free two-edge cover and transforms it with care. Many prior techniques were tight at five quarters, so new ideas were needed to pass it. Approximation ratios measure how close a fast algorithm provably gets to the unreachable optimum. Survivable network design protects power grids, transport, and data backbones. Even a hairline improvement resets what the field believes possible.
Catalog record
| CREATOR | Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 367 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-19655