论文标题
斯坦纳树增强问题的近似算法
Approximation algorithms for Steiner Tree Augmentation Problems
论文作者
论文摘要
在Steiner树增强问题（stap）中，给我们一个图形$ g =（v，e）$，一组终端$ r \ subseteq v $，以及steiner树$ t $ t $ spanning $ r $。边缘$ l：= e \ setMinus e（t）$称为链接，并具有非负成本。目标是通过添加最低成本链接来增强$ t $，以便每对顶点之间有2个边缘 - 偶数路径，$ r $。这个问题是可生存的网络设计问题的特殊情况，可以使用迭代舍入〜\ cite {j2001}将其近似于2倍。 我们给出了第一个多项式时间算法，用于近似值比2更好。特别是，我们达到了$（1.5 + \ varepsilon）$的近似值。为此，我们采用了〜\ cite {tz2022}的局部搜索方法来解决树增强问题，并将其主要分解定理从链接（尺寸2）概括为超链接。 我们还考虑了淋巴结加权的Steiner树增强问题（NW-stap），其中非末端节点的成本非末端。我们寻求最便宜的子集$ s \ subseteq v \ setminus r $ $，以便$ g [r \ cup s] $是2边连接的。使用nutov〜 \ cite {n2010}的结果，存在$ o（\ log | r |）$ - 近似此问题。我们使用利用贪婪的算法利用了最佳解决方案的蜘蛛分解，为NW-stap提供了$ O（\ log^2（| r |））$ - 近似算法。
In the Steiner Tree Augmentation Problem (STAP), we are given a graph $G = (V,E)$, a set of terminals $R \subseteq V$, and a Steiner tree $T$ spanning $R$. The edges $L := E \setminus E(T)$ are called links and have non-negative costs. The goal is to augment $T$ by adding a minimum cost set of links, so that there are 2 edge-disjoint paths between each pair of vertices in $R$. This problem is a special case of the Survivable Network Design Problem, which can be approximated to within a factor of 2 using iterative rounding~\cite{J2001}. We give the first polynomial time algorithm for STAP with approximation ratio better than 2. In particular, we achieve an approximation ratio of $(1.5 + \varepsilon)$. To do this, we employ the Local Search approach of~\cite{TZ2022} for the Tree Augmentation Problem and generalize their main decomposition theorem from links (of size two) to hyper-links. We also consider the Node-Weighted Steiner Tree Augmentation Problem (NW-STAP) in which the non-terminal nodes have non-negative costs. We seek a cheapest subset $S \subseteq V \setminus R$ so that $G[R \cup S]$ is 2-edge-connected. Using a result of Nutov~\cite{N2010}, there exists an $O(\log |R|)$-approximation for this problem. We provide an $O(\log^2 (|R|))$-approximation algorithm for NW-STAP using a greedy algorithm leveraging the spider decomposition of optimal solutions.
