Erratum to “Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems”

Alice Paul (), Daniel Freund (), Aaron Ferber (), David B. Shmoys () and David P. Williamson ()
Additional contact information
Alice Paul: Biostatistics, Brown University, Providence, Rhode Island 02912
Daniel Freund: Operations Management, MIT Sloan School of Management, Cambridge, Massachusetts 02142
Aaron Ferber: Center for Artificial Intelligence in Society, University of Southern California, Los Angeles, California 90089
David B. Shmoys: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14850
David P. Williamson: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14850

Mathematics of Operations Research, 2023, vol. 48, issue 4, 2304-2307

Abstract: There is an error in our paper [Paul A, Freund D, Ferber A, Shmoys DB, Williamson DP (2020) Budgeted prize-collecting traveling salesman and minimum spanning tree problems. Math. Oper. Res. 45(2):576–590]. In that paper, we consider constrained versions of the prize-collecting traveling salesman and the prize-collecting minimum spanning tree problems. The goal is to maximize the number of vertices in the returned tour/tree subject to a bound on the tour/tree cost. Rooted variants of the problems have the additional constraint that a given vertex, the root, must be contained in the tour/tree. In our previous paper, we present a 2-approximation algorithm for the rooted and unrooted versions of both the tree and tour variants using a parameterized primal–dual approach. Here, we illustrate an error in the proof of a lemma for the rooted version of the algorithm and show that the algorithm has no finite approximation guarantee for the rooted version of the problem. We also show that the lemma and the approximation guarantee of 2 continue to hold true for the unrooted version. This leaves the best-known approximations for the rooted tour an established ( 2 + ϵ ) -approximation algorithm and for the tree variant a previously published poly-log approximation algorithm.

Keywords: Primary: 68W25; secondary: 05C85; approximation algorithms; traveling salesman problem; constrained optimization (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1340 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:4:p:2304-2307

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().