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: Data Science Initiative, Brown University, Providence, Rhode Island 02912;
Daniel Freund: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142;
Aaron Ferber: Operations Research and Information Engineering, Cornell University, Ithaca, New York 14850
David B. Shmoys: Operations Research and Information Engineering, Cornell University, Ithaca, New York 14850
David P. Williamson: Operations Research and Information Engineering, Cornell University, Ithaca, New York 14850

Mathematics of Operations Research, 2020, vol. 45, issue 2, 576-590

Abstract: 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. We present a 2-approximation algorithm for the rooted and unrooted versions of both the tree and tour variants. The algorithm is based on a parameterized primal–dual approach. It relies on first finding a threshold value for the dual variable corresponding to the budget constraint in the primal and then carefully constructing a tour/tree that is, in a precise sense, just within budget. We improve upon the best-known guarantee of 2 + ε for the rooted and unrooted tour versions and 3 + ε for the rooted and unrooted tree versions. Our analysis extends to the setting with weighted vertices, in which we want to maximize the total weight of vertices in the tour/tree. Interestingly enough, the algorithm and analysis for the rooted case and the unrooted case are almost identical.

Keywords: approximation algorithms; traveling salesman problem; constrained optimization (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2019.1002 (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:45:y:2020:i:2:p:576-590

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 ().