IEEE - Institute of Electrical and Electronics Engineers, Inc. - Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP

IEEE 50th Annual Symposium on Foundations of Computer Science (FOCS 2009)

Author(s): A. Archer ; M.H. Bateni ; M.T. Hajiaghayi ; H. Karloff
Sponsor(s): IEEE Comput. Soc. Tech. Comm. Math. Found. Comput.
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 October 2009
Conference Location: Atlanta, GA, USA
Conference Date: 25 October 2009
Page(s): 427 - 436
ISBN (Paper): 978-1-4244-5116-6
ISSN (Paper): 0272-5428
DOI: 10.1109/FOCS.2009.39
Regular:

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... View More

Advertisement