# Improved Approximation Algorithms for Prize-Collecting Steiner Tree
and TSP

## Nicolaos Matsakis, UC Irvine

We present a paper by A.Archer, M.Bateni, M.Hajiaghayi, H.Karloff,
which provides algorithms having a (2 − ε)
approximation guarantee for the Prize-Collecting versions of the
Traveling Salesman, Steiner Tree and Stroll problems. The algorithms are
based on the Goemans-Williamson 2-approximation algorithm along with the
best approximation algorithms we currently have for each one of the
ordinary versions of these problems. The important part investigated,
is the application of the latter algorithms onto specific subsets of
vertices the former algorithm spans. This survey solves an open problem
standing for more than 15 years in the area of Prize-Collecting
problems, by providing a guarantee which is strictly less than 2.

(Based on a paper by Aaron Archer, MohammadHossein Bateni, Mohammad
Taghi Hajiaghayi, and Howard Karloff from FOCS 2009.)