论文标题
基于恒星收缩的Steiner树的近似算法：统一视图
Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
论文作者
论文摘要
在Steiner树问题中，我们给出了一个边缘加权的无向图$ g =（v，e）$和一组终端$ r \ subseteq v $。任务是找到包含$ r $的$ g $的连接子图，并最大程度地减少其边缘的权重。我们观察到，斯坦纳树的许多近似算法都遵循类似的方案（元算法），并（详尽地）执行类似的例程，我们称之为恒星收缩。在这里，通过恒星收缩，我们的意思是在输入图中找到一个类似星形的子图，最小化其重量与所包含端子数量的比例减去一个。不难看出，著名的MST AppRoximation寻求仅包含两个终端的恒星收缩的最佳恒星。我们对恒星收缩进行了一项经验研究，并在每个恒星收缩中的终端数量上宽松。 Our experiments suggest the following: -- if the algorithm performs star contractions exhaustively, the quality of the solution is usually slightly better than Zelikovsky's 11/6-approximation algorithm, -- on average the quality of the solution returned by the MST-approximation algorithm improves with every star contraction, -- the same holds for iterated MST (MST+), which outperforms MST in every measurement while保持非常快的运行时间（平均$ \ sim 3 \ times $比MST慢） - 平均而言，通过详尽执行星星收缩获得的解决方案的质量比最初的MST-MST-Approximation高约16 \％，并且 - 我们提出了一种更精确的方法，以在平均$ $ $ $ $ $ $ $ $ $ $ $ $上找到一个更高的改进的星星，从而稍微找到更好的解决方案。此外，我们提出了Zelikovsky的11/6- Approximation算法的两种改进，并从经验上证实，这些解决方案返回的解决方案的质量比以前算法返回的溶液返回的质量要好。
In the Steiner Tree problem we are given an edge weighted undirected graph $G = (V,E)$ and a set of terminals $R \subseteq V$. The task is to find a connected subgraph of $G$ containing $R$ and minimizing the sum of weights of its edges. We observe that many approximation algorithms for Steiner Tree follow a similar scheme (meta-algorithm) and perform (exhaustively) a similar routine which we call star contraction. Here, by a star contraction, we mean finding a star-like subgraph in the input graph minimizing the ratio of its weight to the number of contained terminals minus one. It is not hard to see that the well-known MST-approximation seeks the best star to contract among those containing two terminals only. We perform an empirical study of star contractions with the relaxed condition on the number of terminals in each star contraction. Our experiments suggest the following: -- if the algorithm performs star contractions exhaustively, the quality of the solution is usually slightly better than Zelikovsky's 11/6-approximation algorithm, -- on average the quality of the solution returned by the MST-approximation algorithm improves with every star contraction, -- the same holds for iterated MST (MST+), which outperforms MST in every measurement while keeping very fast running time (on average $\sim 3\times$ slower than MST), -- on average the quality of the solution obtained by exhaustively performing star contraction is about 16\% better than the initial MST-approximation, and -- we propose a more precise way to find the so-called improved stars which yield a slightly better solution within a comparable running time (on average $\sim 3\times$ slower). Furthermore, we propose two improvements of Zelikovsky's 11/6-approximation algorithm and we empirically confirm that the quality of the solution returned by any of these is better than the one returned by the former algorithm.
