Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP

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

We present (2 – epsilon)-approximation algorithms for all three problems, connected by a unified technique for improving prize collecting algorithms that allows us to circumvent the integrality gap barrier.

Speaker Details

Mohammad-Taghi Hajiaghayi is a Senior Researcher in the Algorithms and Theoretical Computer Science group at AT&T Labs – Research. In addition, he holds a Research Affiliate position in MIT Computer Science and Artificial Intelligence Laboratory (CSAIL). He is also a Permanent Member of Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers. Before joining to AT&T Research Labs, he was a one-year Postdoctoral Fellow in the School of Computer Science at Carnegie Mellon University (with ALADDIN project) and a one-year Postdoctoral Associate in MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) from which he also earned his Ph.D in 2005. He received the Master’s degree in Computer Science from the University of Waterloo in 2001 and the Bachelor’s degree in Computer Engineering from Sharif University of Technology in 2000. During his Ph.D. studies, he also worked at the IBM T.J. Watson Research Center (Department of Mathematical Sciences) and at the Microsoft Research Center (Theory group). Dr. Hajiaghayi’s research interests are network design, algorithmic graph theory, combinatorial optimizations and approximation algorithms, distributed and mobile computing, computational geometry and embeddings, game theory and combinatorial auctions, and random structures and algorithms.

Date:
Speakers:
Mohammad Taghi Hajiaghayi
Affiliation:
AT&T Labs

    • Portrait of Jeff Running

      Jeff Running