IMPROVED APPROXIMATION ALGORITHMS FOR PRIZE-COLLECTING STEINER TREE AND TSP
We study the PRIZE-COLLECTING STEINER TREE (PCST), PRIZE-COLLECTING TRAVELING SALESMAN (PCTSP), and PRIZE-COLLECTING PATH (PC-PATH) problems. Given a graph (V, E) with a cost on each edge and a penalty (a.k.a. prize) on each node, the goal is to find a tree (for PCST), cycle (for PCTSP), or path (for PC-PATH) that minimizes the sum of the edge costs in the tree/cycle/path and the penalties of the nodes not spanned by it. In addition to being a useful theoretical tool for helping to solve other optimization problems, PCST has been applied fruitfully by AT&T to the optimization of real-world telecommunications networks. The most recent improvements for the first two problems, a 2-approximation algorithm for each, appeared first in 1992; a 2-approximation for PC-PATH appeared in 2003. The natural linear programming relaxation of PCST has an integrality gap of 2, which has been a barrier to further improvements for this problem. We present (2-epsilon)-approximation algorithms for all three problems, connected by a unified technique for improving prize-collecting algorithms that allows us to circumvent the integrality gap barrier. Specifically, our approximation ratio for PRIZE-COLLECTING STEINER TREE is below 1.9672.
approximation algorithms prize-collecting steiner tree traveling salesman