The prize collecting Steiner tree problem: theory and practice 论文

摘要

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 further modified so that, without an increase in running time, it becomes a 2-approximation algorithm for finding the bes...