Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
SIAM Journal on Computing · 30.06.2023 · 52 (3) · 718-739
DOI: 10.1137/21m1421143 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 23.05.2023. Verfasst von Jarosław Byrka und 2 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 36 Literaturangaben. Gefördert von: Narodowe Centrum Nauki, SNF Excellence.
Abstract (Originalsprache)
The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The connectivity augmentation problem ([Formula: see text]) is arguably one of the most basic problems in this area: given a [Formula: see text](-edge)-connected graph [Formula: see text] and a set of extra edges ( links), select a minimum cardinality subset [Formula: see text] of links such that adding [Formula: see text] to [Formula: see text] increases its edge connectivity to [Formula: see text]. Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is 2, and this can be achieved with multiple approaches (the first such result is in [G. N. Frederickson and Jájá, SIAM J. Comput., 10 (1981), pp. 270–283]. It is known [E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov, Studies in Discrete Optimization, Nauka, Moscow, 1976, pp. 290–306] that [Formula: see text] can be reduced to the case [Formula: see text], also known as the t ree augmentation problem ([Formula: see text]) for odd [Formula: see text], and to the case [Formula: see text], also known as the c actus augmentation problem ([Formula: see text]) for even [Formula: see text]. Prior to the conference version of this paper [J. Byrka, F. Grandoni, and A. Jabal Ameli, STOC’20, ACM, New York, 2020, pp. 815–825], several better than 2 approximation algorithms were known for [Formula: see text], culminating with a recent [Formula: see text] approximation [F. Grandoni, C. Kalaitzis, and R. Zenklusen, STOC’18, ACM, New York, 1918, pp. 632–645]. However, for [Formula: see text] the best known approximation was 2. In this paper we breach the 2 approximation barrier for [Formula: see text], hence, for [Formula: see text], by presenting a polynomial-time [Formula: see text] approximation. From a technical point of view, our approach deviates quite substantially from previous work. In particular, the better-than-2 approximation algorithms for [Formula: see text] either exploit greedy-style algorithms or are based on rounding carefully designed LPs. We instead use a reduction to the Steiner tree problem which was previously used in parameterized algorithms [Basavaraju et al., ICALP ’14, Springer, Berlin, 2014, pp. 800–811]. This reduction is not approximation preserving, and using the current best approximation factor for a Steiner tree [Byrka et al., J. ACM, 60 (2013), 6] as a black box would not be good enough to improve on 2. To achieve the latter goal, we “open the box” and exploit the specific properties of the instances of a Steiner tree arising from [Formula: see text]. In our opinion this connection between approximation algorithms for survivable network design and Steiner-type problems is interesting, and might lead to other results in the area.
Förderung
- Narodowe Centrum Nauki
- SNF Excellence
Zitieren
APA
Byrka, J., Grandoni, F., & Ameli, A. J. (2023). Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree. SIAM Journal on Computing, 52(3), 718-739. https://doi.org/10.1137/21m1421143
Vancouver
Byrka J, Grandoni F, Ameli AJ. Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree. SIAM Journal on Computing. 2023;52(3):718-739. doi:10.1137/21m1421143
BibTeX
@article{Byrka2023,
author = {Byrka, Jarosław and Grandoni, Fabrizio and Ameli, Afrouz Jabal},
title = {Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree},
journal = {SIAM Journal on Computing},
year = {2023},
volume = {52},
number = {3},
pages = {718--739},
doi = {10.1137/21m1421143}
}
EUVIMED