Approximation Algorithms for Steiner Connectivity Augmentation
Mathematics of Operations Research · 06.07.2026
DOI: 10.1287/moor.2024.0837 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics of Operations Research, online erschienen am 06.07.2026. Verfasst von Daniel Hathcock und 1 weiteren Autor:innen. Die Arbeit nennt 29 Literaturangaben.
Abstract (Originalsprache)
We consider connectivity augmentation problems in the Steiner setting. In the Steiner Augmentation of a Graph problem (k-SAG), we are given a k-edge-connected graph H, which we seek to augment by including links of minimum cost so that the edge connectivity between nodes of H increases by 1. Unlike the standard Connectivity Augmentation Problem, links to Steiner nodes outside H are available for the augmentation. If H is not assumed to be globally k-edge connected but rather Steiner k-edge connected on some set of terminals R, then we obtain the more general Steiner Connectivity Augmentation Problem (k-SCAP). We give a [Formula: see text]-approximation for the Steiner Ring Augmentation Problem (SRAP). This yields a polynomial time algorithm with approximation ratio [Formula: see text] for 2-SCAP. We obtain an improved approximation guarantee for SRAP when the ring consists of only terminals, yielding a [Formula: see text]-approximation for k-SAG for any k. Funding: This work was supported by National Science Foundation Graduate Research Fellowship Program [DGE-2140739].
Zitieren
APA
Hathcock, D., & Zlatin, M. (2026). Approximation Algorithms for Steiner Connectivity Augmentation. Mathematics of Operations Research. https://doi.org/10.1287/moor.2024.0837
Vancouver
Hathcock D, Zlatin M. Approximation Algorithms for Steiner Connectivity Augmentation. Mathematics of Operations Research. 2026. doi:10.1287/moor.2024.0837
BibTeX
@article{Hathcock2026,
author = {Hathcock, Daniel and Zlatin, Michael},
title = {Approximation Algorithms for Steiner Connectivity Augmentation},
journal = {Mathematics of Operations Research},
year = {2026},
doi = {10.1287/moor.2024.0837}
}
EUVIMED