When

Start: 01/26/2011 - 4:15pm

End : 01/26/2011 - 5:00pm

End : 01/26/2011 - 5:00pm

Category

Colloquium

Speaker

Aaron Archer (AT&T Shannon Research Laboratory)

Abstract

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).

Where

Roberts North 15, Claremont McKenna College