Improved Approximation Algorithms for the Prize-Collecting Steiner Tree Problem

Start: 01/26/2011 - 4:15pm
End  : 01/26/2011 - 5:00pm


Aaron Archer (AT&T Shannon Research Laboratory)


Given a graph (V, E) with a cost on each edge and a penalty (a.k.a. prize) on each node, the
prize-collecting Steiner tree (PCST) problem asks for the tree that minimizes the sum of the edge
costs in the tree 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.
This problem is NP-hard, so research has focused on approximation: designing algorithms that
run in polynomial time and return a solution guaranteed to be within some multiplicative factor of
the optimum. The most recent improvement was the famous 2-approximation algorithm of Goemans
and Williamson, which first appeared in 1992. 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 a 1.9672-approximation algorithm for PCST, using a new technique for improving
prize-collecting algorithms that allows us to circumvent the integrality gap barrier. We have also
applied the same technique to obtain improved approximation algorithms for the prize-collecting
path and traveling salesman problems.
This is joint work with Mohammad Hossein Bateni (Princeton), MohammadTaghi Hajiaghayi
(AT&T), and Howard Karloff (AT&T).


Roberts North 15, Claremont McKenna College