SIAM Journal on Computing · 2011 · 88 citations · 15 references
ComputingComputer ScienceAlgorithmsComputer NetworksOptimizationApproximation AlgorithmsCombinatorial OptimizationDiscrete OptimizationGraph AlgorithmsLinear ProgrammingNetwork OptimizationApproximation Algorithms For Shortest PathsShortest Path ProblemsSteiner Tree ApproximationSteiner Tree ProblemTelecommunications NetworksTraveling Salesman ApproximationTraveling Salesman ProblemTraveling Salesperson Problem Approximation
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.
15
The prize collecting traveling salesman problem
Egon Balas · Networks · 1989 · 564 citations
An 11/6-approximation algorithm for the network steiner problem
Alex Zelikovsky · Algorithmica · 1993 · 338 citations · Full text