Title: Improved approximation algorithms for prize-collecting problems
Speaker: Mohammad Hossein Bateni, Princeton University
Date: Wednesday, February 25, 2009 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
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.