2026-07-23T06:31:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21138 2024-09-23T09:13:17Z ddc:004 open_access

Approximation Algorithms for Steiner Connectivity Augmentation Hathcock, Daniel Zlatin, Michael Approximation Algorithms Steiner Connectivity Network Design We consider connectivity augmentation problems in the Steiner setting, where the goal is to augment the edge-connectivity between a specified subset of terminal nodes. In the Steiner Augmentation of a Graph problem (k-SAG), we are given a k-edge-connected subgraph H of a graph G. The goal is to augment H by including links from G of minimum cost so that the edge-connectivity between nodes of H increases by 1. This is a generalization of the Weighted Connectivity Augmentation Problem, in which only links between pairs of nodes in H are available for the augmentation. In the Steiner Connectivity Augmentation Problem (k-SCAP), we are given a Steiner k-edge-connected graph connecting terminals R, and we seek to add links of minimum cost to create a Steiner (k+1)-edge-connected graph for R. Note that k-SAG is a special case of k-SCAP. The results of Ravi, Zhang and Zlatin for the Steiner Tree Augmentation problem yield a (1.5+ε)-approximation for 1-SCAP and for k-SAG when k is odd [Ravi et al., 2023]. In this work, we give a (1 + ln{2} +ε)-approximation for the Steiner Ring Augmentation Problem (SRAP). This yields a polynomial time algorithm with approximation ratio (1 + ln{2} + ε) for 2-SCAP. We obtain an improved approximation guarantee for SRAP when the ring consists of only terminals, yielding a (1.5+ε)-approximation for k-SAG for any k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Hathcock and Michael Zlatin 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.67 urn:nbn:de:0030-drops-211387 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.67 eng https://creativecommons.org/licenses/by/4.0/legalcode