{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T23:30:54Z","timestamp":1792798254684,"version":"4.5.0"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>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&amp;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 relaxation of PCST has an integrality gap of 2, which has been a barrier to further improvements for this problem. We present $(2-\\epsilon)$-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.<\/jats:p>","DOI":"10.1137\/090771429","type":"journal-article","created":{"date-parts":[[2011,3,29]],"date-time":"2011-03-29T18:45:36Z","timestamp":1301424336000},"page":"309-332","source":"Crossref","is-referenced-by-count":76,"title":["Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP"],"prefix":"10.1137","volume":"40","author":[{"given":"Aaron","family":"Archer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"MohammadHossein","family":"Bateni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Howard","family":"Karloff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,3,29]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"A. Archer, M. Bateni, M. Hajiaghayi, and H. Karloff,\n                      Improved approximation algorithms for prize-collecting Steiner tree and TSP\n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, pp. 427\u2013436.","DOI":"10.1109\/FOCS.2009.39"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"A. Archer and A. Blasiak,\n                      Improved approximation algorithms for the minimum latency problem via prize-collecting strolls\n                      , in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp. 429\u2013447.","DOI":"10.1137\/1.9781611973075.36"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/07068151X"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0693-1"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00010-6"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230190602"},{"key":"R8","unstructured":"P. Berman and V. Ramaiyer,\n                      Improved approximations for the Steiner tree problem\n                      , in Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, 1992, pp. 325\u2013334."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581256"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"J. Byrka, F. Grandoni, T. Rothvo\u00df, and L. Sanit\u00e0,\n                      An improved LP-based approximation for Steiner tree\n                      , in Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, 2010, pp. 583\u2013592.","DOI":"10.1145\/1806689.1806769"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398594"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"K. Chaudhuri, B. Godfrey, S. Rao, and K. Talwar,\n                      Paths, trees, and minimum latency tours\n                      , in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 36\u201345.","DOI":"10.1109\/SFCS.2003.1238179"},{"key":"R13","unstructured":"N. Christofides,\n                      Worst-Case Analysis of a New Heuristic for the Travelling-Salesman Problem\n                      , Technical report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0479-2"},{"key":"R15","unstructured":"P. Feofiloff, C. G. Fernandes, C. E. Ferreira, and J. C. de Pina,\n                      A note on Johnson, Minkoff and Phillips' algorithm for the prize-collecting Steiner tree problem\n                      , arXiv:1004.1437v2 [cs.DS], (2010)."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"H. N. Gabow and S. Pettie,\n                      The dynamic vertex minimum problem and its application to clustering-type approximation algorithms\n                      , in Proceedings of the Eighth Scandinavian Workshop on Algorithm Theory, 2002, pp. 190\u2013199.","DOI":"10.1007\/3-540-45471-3_20"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"N. Garg,\n                      \n                        A 3-approximation for the minimum tree spanning\n                        k\n                        vertices\n                      \n                      , in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, pp. 302\u2013309.","DOI":"10.1109\/SFCS.1996.548489"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"N. Garg,\n                      Saving an epsilon: A 2-approximation for the k-MST problem in graphs\n                      , in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 396\u2013402.","DOI":"10.1145\/1060590.1060650"},{"key":"R19","unstructured":"M. X. Goemans,\n                      Combining approximation algorithms for the prize-collecting TSP\n                      , arXiv:0910.0553v1 [cs.DS], (2009)."},{"key":"R20","unstructured":"M. X. Goemans and D. P. Williamson,\n                      A general approximation technique for constrained forest problems\n                      , in Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, 1992, pp. 307\u2013316."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"R22","unstructured":"A. Hayrapetyan, C. Swamy, and \u00c9. Tardos,\n                      Network design for information networks\n                      , in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 933\u2013942."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90016-I"},{"key":"R24","unstructured":"S. Hougardy and H. J. Pr\u00f6mel,\n                      A $1.598$ approximation algorithm for the Steiner problem in graphs\n                      , in Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, pp. 448\u2013453."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"R26","unstructured":"D. S. Johnson, M. Minkoff, and S. Phillips,\n                      The prize collecting Steiner tree problem: Theory and practice\n                      , in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, pp. 760\u2013769."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01293485"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009758919736"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"H. J. Pr\u00f6mel and A. Steger,\n                      RNC-approximation algorithms for the Steiner problem\n                      , in Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, 1997, pp. 559\u2013570.","DOI":"10.1007\/BFb0023489"},{"key":"R30","unstructured":"G. Robins and A. Zelikovsky,\n                      Improved Steiner tree approximation in graphs\n                      , in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, pp. 770\u2013779."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"A. Zelikovsky,\n                      An $11$\/6-approximation for the Steiner problem on graphs\n                      , in Proceedings of the 4th Czechoslovakian Symposium on Combinatorics, Graphs, and Complexity (1990), Ann. Discrete Math. 51, North\u2013Holland, Amsterdam, 1992, pp. 351\u2013354.","DOI":"10.1016\/S0167-5060(08)70655-1"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187035"},{"key":"R34","unstructured":"A. Zelikovsky,\n                      Better Approximation Bounds for the Network and Euclidean Steiner Tree Problems\n                      , Technical report, University of Virginia, Charlottesville, VA, 1996."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090771429","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:36:13Z","timestamp":1787337373000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090771429"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/090771429"],"URL":"https:\/\/doi.org\/10.1137\/090771429","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}