Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems (vol 45, pg 576, 2020)

• 成果类型: Correction
• 署名作者: Paul, Alice; Freund, Daniel; Ferber, Aaron; Shmoys, David B.; Williamson, David P.
• 署名单位: Brown University; Massachusetts Institute of Technology (MIT); University of Southern California; Cornell University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1340
• 发表日期: 2023
• 页码: 2304-2307

摘要

There is an error in our paper [Paul A, Freund D, Ferber A, Shmoys DB, William-son 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 + is an element of)-approximation algorithm and for the tree variant a previously published poly-log approximation algorithm.