## Samenvatting

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 (CAP) is arguably one of the most basic problems in this area: given a k(-edge)-connected graph G and a set of extra edges (links), select a minimum cardinality subset A of links such that adding A to G increases its edge connectivity to k+1. 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\'aj\' a, 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 CAP can be reduced to the case k = 1, also known as the tree augmentation problem (TAP) for odd k, and to the case k = 2, also known as the cactus augmentation problem (CacAP) for even k. 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 TAP, culminating with a recent 1.458 approximation [F. Grandoni, C. Kalaitzis, and R. Zenklusen, STOC'18, ACM, New York, 1918, pp. 632-645]. However, for CacAP the best known approximation was 2. In this paper we breach the 2 approximation barrier for CacAP, hence, for CAP, by presenting a polynomial-time 2 ln(4) -
_{1120}
^{967} + \varepsilon < 1.91 approximation. From a technical point of view, our approach deviates quite substantially from previous work. In particular, the better-than-2 approximation algorithms for TAP 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 CacAP. 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.

Originele taal-2 | Engels |
---|---|

Pagina's (van-tot) | 718-739 |

Aantal pagina's | 22 |

Tijdschrift | SIAM Journal on Computing |

Volume | 52 |

Nummer van het tijdschrift | 3 |

Vroegere onlinedatum | 2023 |

DOI's | |

Status | Gepubliceerd - jun. 2023 |

### Financiering

*Received by the editors May 25, 2021; accepted for publication (in revised form) December 28, 2022; published electronically May 23, 2023. https://doi.org/10.1137/21M1421143 Funding: The first author was supported by the NCN grant 2015/18/E/ST6/00456. The second and third authors were partially supported by SNF Excellence Grant 200020B 182865/1. \dagger University of Wroc\law, Wroc\law, Poland ([email protected]). \ddagger IDSIA, USI-SUPSI, Lugano-Viganello, Switzerland ([email protected]). \S Eindhoven University of Technology, Eindhoven, Netherlands ([email protected]).

Financiers | Financiernummer |
---|---|

Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung | 200020B 182865/1 |

Narodowe Centrum Nauki | 2015/18/E/ST6/00456 |