论文标题
密集的坦纳问题：近似算法和不可Ximibibibility
Dense Steiner problems: Approximation algorithms and inapproximability
论文作者
论文摘要
Steiner树问题是组合优化的经典问题：目标是通过最小大小的树连接图$ G $中的$ t终端的$ T $。 Karpinski和Zelikovsky（1996）研究了{\ sc Steiner Tree}的$δ$浓度版本，其中每个端子至少具有$δ| v（g）\ setminus t | $ t | $ t $ t $，用于固定$δ> 0 $。他们为这个问题提供了PTA。 我们研究了成对的$δ$ dense {\ sc steiner Forest}的概括，该}要求在$ g $中使用最小尺寸的森林，其中每个终端中的节点套装$ t_1，\ dots，t_k $都连接，$ t_i $ in $ t_i $中的每个末端至少都有$δ| v（g）\ setMinus（t_1 \ cup \ dots \ cup t_k）$，对于每种$ i，j $ in $ \ {1，\ dots，k \} $，带有$ i \ neq j $。我们的第一个结果是所有$δ> 1/2 $的多项式时间近似方案。然后，我们显示$（\ frac {13} {12}+\ varepsilon）$ - $δ= 1/2 $的近似算法和任何$ \ varepsilon> 0 $。我们还考虑了Hauptmann定义的$δ$ - 元集团施泰纳树问题，并表明该问题是$ \ Mathsf {apx} $ - 硬。
The Steiner Tree problem is a classical problem in combinatorial optimization: the goal is to connect a set $T$ of terminals in a graph $G$ by a tree of minimum size. Karpinski and Zelikovsky (1996) studied the $δ$-dense version of {\sc Steiner Tree}, where each terminal has at least $δ|V(G)\setminus T|$ neighbours outside $T$, for a fixed $δ> 0$. They gave a PTAS for this problem. We study a generalization of pairwise $δ$-dense {\sc Steiner Forest}, which asks for a minimum-size forest in $G$ in which the nodes in each terminal set $T_1,\dots,T_k$ are connected, and every terminal in $T_i$ has at least $δ|T_j|$ neighbours in $T_j$, and at least $δ|S|$ nodes in $S = V(G)\setminus (T_1\cup\dots\cup T_k)$, for each $i, j$ in $\{1,\dots, k\}$ with $i\neq j$. Our first result is a polynomial-time approximation scheme for all $δ> 1/2$. Then, we show a $(\frac{13}{12}+\varepsilon)$-approximation algorithm for $δ= 1/2$ and any $\varepsilon > 0$. We also consider the $δ$-dense Group Steiner Tree problem as defined by Hauptmann and show that the problem is $\mathsf{APX}$-hard.
