Approximation Algorithms for Steiner Connectivity Augmentation

• 成果类型: Article; Early Access
• 署名作者: Hathcock, Daniel; Zlatin, Michael
• 署名单位: Carnegie Mellon University; Carnegie Mellon University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2024.0837
• 发表日期: 2026-07-06
• 关键词: approximation algorithms; Combinatorial Optimization; Network design; TREE AUGMENTATION; ratio

摘要

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 (1 + ln 2 + )-approximation pound for the Steiner Ring Augmentation Problem (SRAP). This yields a polynomial time algorithm with approximation ratio (1 + ln 2+ ) pound for 2-SCAP. We obtain an improved approximation guarantee for SRAP when the ring consists of only terminals, yielding a (1:5 + )-approximation pound for k-SAG for any k.