### DIMACS Theoretical Computer Science Seminar

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.