Improved Approximations for Flexible Network Design
<|reference_start|>Improved Approximations for Flexible Network Design: Flexible network design deals with building a network that guarantees some connectivity requirements between its vertices, even when some of its elements (like vertices or edges) fail. In particular, the set of edges (resp. vertices) of a given graph are here partitioned into safe and unsafe. The goal is to identify a minimum size subgraph that is 2-edge-connected (resp. 2-vertex-connected), and stay so whenever any of the unsafe elements gets removed.   In this paper, we provide improved approximation algorithms for flexible network design problems, considering both edge-connectivity and vertex-connectivity, as well as connectivity values higher than 2. For the vertex-connectivity variant, in particular, our algorithm is the first with approximation factor strictly better than 2.<|reference_end|>
@article{hyatt-denesik2024improved,
    title={Improved Approximations for Flexible Network Design},
    author={Dylan Hyatt-Denesik, Afrouz Jabal Ameli, Laura Sanita},
    journal={arXiv preprint arXiv:2404.08972},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.08972},
    primaryClass={cs.DS}
}