The prize collecting Steiner tree problem: theory and practice
The prize collecting Steiner tree problem: theory and practice
复制标题
DOI：
--
复制
发表时间：
2000-02
期刊：
影响因子：
--
通讯作者：
David S. Johnson;M. Minkoff;Steven J. Phillips
中科院分区：
文献类型：
--
作者：
David S. Johnson;M. Minkoff;Steven J. Phillips
我们考虑了关于获奖收集Steiner树问题的变体以及Goemans和Williamson为其设计的原始-对偶2-近似算法。我们为算法引入了一种改进的剪枝规则，该规则略微更快，并提供了至少同样好且通常明显更好的解决方案。在选取的以县街道地图为底层图形的真实世界实例上，标准目标函数的改进范围从1.7%到9.2%。对于互补的“净值”目标函数和随机生成的实例，获得了显著更好的改进。我们还证明了修改GoemansWilliamson算法的生长阶段以使其独立于根顶点的选择并不显著地影响算法的最坏情况保证或在实践中的行为。所得到的算法可以进一步修改，以便在不增加运行时间的情况下，它成为在所有根选择上寻找最佳子树的2-近似算法。在论文的第二部分，我们考虑了定额和预算版本的问题。第一种是寻找边代价最小的树，该树的顶点的总奖金至少是给定的配额；第二种是寻找边代价最大的树，给定总边代价在给定的预算之内。配额问题是k-MST问题的推广，我们观察到该问题的常数因子近似算法如何推广到该问题。我们还展示了如何从Gaxg的k-MST的3-近似算法中推导出(无根)预算问题的(5？e)近似算法。这些算法都不太可能在实践中使用，但我们展示了如何将它们背后的一般方法(包括使用递增的获奖倍增器序列执行多次GoemansWiUiamson算法)合并到实用的启发式中。我们还揭示了这种方法生成(和使用)的成本/收益权衡曲线的一些令人惊讶的特性。1[6，7](PCST)问题，给出一个图G=(V，E)，每个边e 6 E的一个非负边代价c(E)，每个顶点v 6 V的一个非负顶点奖励p(V)，以及一个指定的根顶点vo 6 V。在本文中，我们将基于这个场景考虑四个不同的优化问题，第一个是在[6，7]中最初研究的问题：“，/~T实验室，新泽西州弗洛勒姆公园公园大道180号，C239室，07932。电邮：dsj@research.att.com？麻省理工学院实验室。计算机科学，马萨诸塞州剑桥市科技广场545号，邮编：02139。Emaih Mariam@theory.lcs.mit.edu SAT&T实验室，新泽西州弗罗拉姆公园公园大道180号A003室，邮编：07932。Emaih Phillips@reseoxch.att.com Steven Phillips 1.Goemans-WiUiamson最小化问题：找到G的一个子树T‘=(V’，E‘)，使得树中的边的代价和不在树中的顶点的奖赏最小化，即t最小化GW(T’)=Z c(E)+Z p(V)
We consider variants on the Prize Collecting Steiner Tree problem and on the primal-dual 2-approximation algorithm devised for it by Goemans and Williamson. We introduce an improved pruning rule for the algorithm that is slightly faster and provides solutions that are at least as good and typically significantly better. On a selection of real-world instances whose underlying graphs are county street maps, the improvement in the standard objective function ranges from 1.7% to 9.2%. Substantially better improvements are obtained for the complementary "net worth" objective function and for randomly generated instances. We also show that modifying the growth phase of the GoemansWilliamson algorithm to make it independent of the choice of root vertex does not significantly affect the algorithm's worst-case guarantee or behavior in practice. The resulting algorithm can be fttrther modified so that, without an increase in running time, it becomes a 2-approximation algorithm for finding the best subtree over all choices of root. In the second part of the paper, we consider quota and budget versions of the problem. In the first, one is looking for the tree with minimum edge cost that contains vertices whose total prize is at least a given quota; in the second one is looking for the tree with maximum prize, given that the total edge cost is within a given budget. The quota problem is a generalization of the k-MST problem, and we observe how constant-factor approximation algorithms for that problem can be extended to it. We also show how a (5 ÷ e)approximation algorithm for the (unrooted) budget problem can be derived from Gaxg's 3-approximation algorithm for the k-MST. None of these algorithms are likely to be used in ~ ractice, but we show how the general approach behind them which involves performing multiple runs of the GoemansWiUiamson algorithm using an increasing sequence of prizemultipliers) can be incorporated into a practical heuristic. We also uncover some surprising properties of the cost/prize tradeoff curves generated (and used) by this approach. 1 Prob lem Def in i t ions In the Prize Collecting Steiner Tree" (PCST) problem, one is given a graph G = (V, E) , a non-negative edge cost c(e) for each edge e 6 E , a non-negative vertex prize p(v) for each vertex v 6 V, and a specified root vertex vo 6 V. In this paper we shall consider four different optimization problems based on this scenario, the first being the one initially studied in [6, 7]: " ¢ / ~ T Labs, Room C239, 180 Park Avenue, Florham Park, NJ 07932. Email: dsj@research.att.com ?MIT Lab. for Computer Science, 545 Tech Square, Cambridge, MA 02139. Emaih mariam@theory.lcs.mit.edu SAT&T Labs, Room A003, 180 Park Avenue, Florham Park, NJ 07932. Emaih phillips@reseoxch.att.com Steven Phillips 1. The Goemans-WiUiamson Minimization problem: Find a subtree T ' = (V',E') of G tha t minimizes the cost of the edges in the tree plus the prizes of the vertices not in the tree, i.e., tha t minimizes GW(T') = Z c(e) + Z p(v)