Title: Improved approximation algorithms for prize-collecting problems

Speaker: Mohammad Hossein Bateni 

ABSTRACT:
We study the prize-collecting versions of the Steiner tree (PCST) and 
traveling salesman (PCTSP) problems: given a graph (V, E) with costs on each 
edge and a penalty on each node, the goal is to find a tree (for PCST) or 
cycle (for PCTSP), that minimizes the sum of the edge costs in the tree/cycle 
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 to the optimization of real-world 
telecommunications networks. The most recent improvements for these problems, 
giving a 2-approximation algorithm for each, appeared first in 1992. The 
natural linear programming (LP) relaxation of PCST has an integrality ratio 
of 2, which has been a barrier to further improvements for this problem.

We present (2-epsilon)-approximation algorithms for both problems, connected 
by a general technique for improving prize-collecting algorithms that manages 
to circumvent the integrality ratio barrier.