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.)