IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v45y2020i2p576-590.html
   My bibliography  Save this article

Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems

Author

Listed:
  • 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)

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.

Suggested Citation

  • Alice Paul & Daniel Freund & Aaron Ferber & David B. Shmoys & David P. Williamson, 2020. "Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems," Mathematics of Operations Research, INFORMS, vol. 45(2), pages 576-590, May.
    • Handle: RePEc:inm:ormoor:v:45:y:2020:i:2:p:576-590
    DOI: 10.1287/moor.2019.1002
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2019.1002
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2019.1002?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    2. Kaspi, Mor & Raviv, Tal & Tzur, Michal, 2016. "Detection of unusable bicycles in bike-sharing systems," Omega, Elsevier, vol. 65(C), pages 10-16.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Qing Zhao & Zhen Li & Jianqiang Li & Jianxiong Guo & Xingjian Ding & Deying Li, 2025. "Uav trajectory optimization for maximizing the ToI-based data utility in wireless sensor networks," Journal of Combinatorial Optimization, Springer, vol. 49(3), pages 1-25, April.
    2. Ben Hermans & Roel Leus & Jannik Matuschke, 2022. "Exact and Approximation Algorithms for the Expanding Search Problem," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 281-296, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. S Salhi & A Al-Khedhairi, 2010. "Integrating heuristic information into exact methods: The case of the vertex p-centre problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1619-1631, November.
    2. Rafael Blanquero & Emilio Carrizosa & Amaya Nogales-Gómez & Frank Plastria, 2014. "Single-facility huff location problems on networks," Annals of Operations Research, Springer, vol. 222(1), pages 175-195, November.
    3. Martins, Francisco Leonardo Bezerra & do Nascimento, José Cláudio, 2022. "Power law dynamics in genealogical graphs," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 596(C).
    4. Marjan Marzban & Qian-Ping Gu & Xiaohua Jia, 2016. "New analysis and computational study for the planar connected dominating set problem," Journal of Combinatorial Optimization, Springer, vol. 32(1), pages 198-225, July.
    5. Ferrer, José M. & Martín-Campo, F. Javier & Ortuño, M. Teresa & Pedraza-Martínez, Alfonso J. & Tirado, Gregorio & Vitoriano, Begoña, 2018. "Multi-criteria optimization for last mile distribution of disaster relief aid: Test cases and applications," European Journal of Operational Research, Elsevier, vol. 269(2), pages 501-515.
    6. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    7. Roberto Tadei & Guido Perboli & Francesca Perfetti, 2017. "The multi-path Traveling Salesman Problem with stochastic travel costs," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 3-23, March.
    8. Lancia, Giuseppe & Vidoni, Paolo, 2020. "Finding the largest triangle in a graph in expected quadratic time," European Journal of Operational Research, Elsevier, vol. 286(2), pages 458-467.
    9. Oya Ekin Karaşan & A. Ridha Mahjoub & Onur Özkök & Hande Yaman, 2014. "Survivability in Hierarchical Telecommunications Networks Under Dual Homing," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 1-15, February.
    10. Paredes-Belmar, Germán & Montero, Elizabeth & Lüer-Villagra, Armin & Marianov, Vladimir & Araya-Sassi, Claudio, 2022. "Vehicle routing for milk collection with gradual blending: A case arising in Chile," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1403-1416.
    11. Thanh Tan Doan & Nathalie Bostel & Minh Hoàng Hà & Vu Hoang Vuong Nguyen, 2023. "New mixed integer linear programming models and an iterated local search for the clustered traveling salesman problem with relaxed priority rule," Journal of Combinatorial Optimization, Springer, vol. 46(1), pages 1-27, August.
    12. Pop, Petrică C. & Cosma, Ovidiu & Sabo, Cosmin & Sitar, Corina Pop, 2024. "A comprehensive survey on the generalized traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 314(3), pages 819-835.
    13. F. Angel-Bello & Y. Cardona-Valdés & A. Álvarez, 2019. "Mixed integer formulations for the multiple minimum latency problem," Operational Research, Springer, vol. 19(2), pages 369-398, June.
    14. Jean-Charles Créput & Amir Hajjam & Abderrafiaa Koukam & Olivier Kuhn, 2012. "Self-organizing maps in population based metaheuristic to the dynamic vehicle routing problem," Journal of Combinatorial Optimization, Springer, vol. 24(4), pages 437-458, November.
    15. Jian Lin & Xiangfei Zeng & Jianxun Liu & Keqin Li, 2022. "Angular bisector insertion algorithm for solving small-scale symmetric and asymmetric traveling salesman problem," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 235-252, January.
    16. Leticia Vargas & Nicolas Jozefowiez & Sandra Ulrich Ngueveu, 2017. "A dynamic programming operator for tour location problems applied to the covering tour problem," Journal of Heuristics, Springer, vol. 23(1), pages 53-80, February.
    17. Afsaneh Amiri & Majid Salari, 2019. "Time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 415-468, June.
    18. Marcel Turkensteen & Dmitry Malyshev & Boris Goldengorin & Panos M. Pardalos, 2017. "The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems," Journal of Global Optimization, Springer, vol. 68(3), pages 601-622, July.
    19. A. S. Santos & A. M. Madureira & M. L. R. Varela, 2018. "The Influence of Problem Specific Neighborhood Structures in Metaheuristics Performance," Journal of Mathematics, Hindawi, vol. 2018, pages 1-14, July.
    20. Markus Sinnl, 2021. "Mixed-integer programming approaches for the time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(2), pages 497-542, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:45:y:2020:i:2:p:576-590. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.