@article{TD:7LJU9U, att_abstract={We study the prize-collecting Steiner tree (PCST), prize-collecting traveling salesman (PCTSP), and prize-collecting path (PC-Path) problems. Given a graph (V,E) with a cost 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 path (for PC-Path) that minimizes the sum of the edge costs in the tree/cycle/path 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, a 2-approximation algorithm for each, appeared first in 1992; a 2-approximation for PC-Path 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-eps)-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. Specifically, our approximation ratio for prize-collecting Steiner tree is below 1.9672. }, att_authors={aa1327, hk1971, mh0357}, att_categories={C_CCF.1, C_CCF.7, C_CCF.8}, att_copyright={Society for Industrial and Applied Mathematics}, att_copyright_notice={}, att_donotupload={}, att_private={false}, att_projects={}, att_tags={prize-collecting, approximation algorithms, Steiner tree problem, traveling salesman problem}, att_techdoc={true}, att_techdoc_key={TD:7LJU9U}, att_url={http://web1.research.att.com:81/techdocs_downloads/TD:7LJU9U_DS1_2010-08-18T15:47:35.638Z.pdf}, author={Aaron Archer AND MohammadHossein Bateni AND Mohammad Hajiaghayi AND Howard Karloff}, institution={{SIAM Journal on Computing}}, journal={{SIAM} Journal on Computing}, month={March}, number=2, pages={309-332}, title={Improved Approximation Algorithms for Prize-Collecting {Steiner} Tree and {TSP}}, volume=40, year=2011, }