Search Results

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.