@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,
}