EUVIMEDEUVIMED entdecken
Crossref

Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree

Jarosław Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →