Document Open Access Logo

Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else

Authors Evripidis Bampis , Bruno Escoffier , Themis Gouleakis , Niklas Hahn , Kostas Lakis , Golnoosh Shahkarami , Michalis Xefteris

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.12.pdf
  • Filesize: 0.83 MB
  • 17 pages

Document Identifiers

Author Details

Evripidis Bampis
  • Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
Bruno Escoffier
  • Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
  • Institut Universitaire de France, Paris, France
Themis Gouleakis
  • National University of Singapore, Singapore
Niklas Hahn
  • Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
Kostas Lakis
  • ETH Zürich, Switzerland
Golnoosh Shahkarami
  • Max-Planck-Institut für Informatik, Universität des Saarlandes, Saarbrücken, Germany
Michalis Xefteris
  • Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

Acknowledgements

This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR). Kostas Lakis gratefully acknowledges financial support from the Foundation for Education and European Culture, Athens, Greece. Themis Gouleakis was supported by the National Research Foundation Fellowship for AI (Award NRF-NRFFAI-0002), an Amazon Research Award, and a Google South & Southeast Asia Research Award.

Cite As Get BibTex

Evripidis Bampis, Bruno Escoffier, Themis Gouleakis, Niklas Hahn, Kostas Lakis, Golnoosh Shahkarami, and Michalis Xefteris. Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.12

Abstract

We study the Online Traveling Salesperson Problem (OLTSP) with predictions. In OLTSP, a sequence of initially unknown requests arrive over time at points (locations) of a metric space. The goal is, starting from a particular point of the metric space (the origin), to serve all these requests while minimizing the total time spent. The server moves with unit speed or is "waiting" (zero speed) at some location. We consider two variants: in the open variant, the goal is achieved when the last request is served. In the closed one, the server additionally has to return to the origin. We adopt a prediction model, introduced for OLTSP on the line [Gouleakis et al., 2023], in which the predictions correspond to the locations of the requests and extend it to more general metric spaces.
We first propose an oracle-based algorithmic framework, inspired by previous work [Bampis et al., 2023]. This framework allows us to design online algorithms for general metric spaces that provide competitive ratio guarantees which, given perfect predictions, beat the best possible classical guarantee (consistency). Moreover, they degrade gracefully along with the increase in error (smoothness), but always within a constant factor of the best known competitive ratio in the classical case (robustness). 
Having reduced the problem to designing suitable efficient oracles, we describe how to achieve this for general metric spaces as well as specific metric spaces (rings, trees and flowers), the resulting algorithms being tractable in the latter case. The consistency guarantees of our algorithms are tight in almost all cases, and their smoothness guarantees only suffer a linear dependency on the error, which we show is necessary. Finally, we provide robustness guarantees improving previous results.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Online algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • TSP
  • Online algorithms
  • Learning-augmented algorithms
  • Algorithms with predictions
  • Competitive analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Luca Allulli, Giorgio Ausiello, and Luigi Laura. On the power of lookahead in on-line vehicle routing problems. In COCOON, 2005. Google Scholar
  2. Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc P. Renault. Online computation with untrusted advice. In ITCS, 2020. Google Scholar
  3. Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In ICML, 2020. Google Scholar
  4. Antonios Antoniadis, Peyman Jabbarzade Ganje, and Golnoosh Shahkarami. A novel prediction setup for online speed-scaling. CoRR abs/2112.03082, 2021. URL: https://arxiv.org/abs/2112.03082.
  5. Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. In NeurIPS, 2020. Google Scholar
  6. Sanjeev Arora. Polynomial time approximation schemes for euclidean TSP and other geometric problems. In FOCS, 1996. Google Scholar
  7. Sanjeev Arora. Nearly linear time approximation schemes for euclidean TSP and other geometric problems. In FOCS, 1997. Google Scholar
  8. Norbert Ascheuer, Martin Grötschel, Sven O. Krumke, and Jörg Rambau. Combinatorial online optimization. In Peter Kall and Hans-Jakob Lüthi, editors, Operations Research Proceedings 1998, pages 21-37, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. Google Scholar
  9. Giorgio Ausiello, Marc Demange, Luigi Laura, and Vangelis Paschos. Algorithms for the on-line quota traveling salesman problem. Inf. Process. Lett., 92(2):89-94, 2004. Google Scholar
  10. Giorgio Ausiello, Esteban Feuerstein, Stefano Leonardi, Leen Stougie, and Maurizio Talamo. Algorithms for the on-line travelling salesman. Algorithmica, 29:560-581, 2001. Google Scholar
  11. Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. In NeurIPS, 2020. Google Scholar
  12. Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. In NeurIPS, 2020. Google Scholar
  13. Evripidis Bampis, Bruno Escoffier, Themis Gouleakis, Niklas Hahn, Kostas Lakis, Golnoosh Shahkarami, and Michalis Xefteris. Learning-augmented online TSP on rings, trees, flowers and (almost) everywhere else. CoRR, abs/2305.02169, 2023. URL: https://arxiv.org/abs/2305.02169.
  14. Evripidis Bampis, Bruno Escoffier, Niklas Hahn, and Michalis Xefteris. Online TSP with Known Locations. To appear in WADS, 2023. CoRR abs/2210.14722. Google Scholar
  15. Evripidis Bampis, Bruno Escoffier, and Michalis Xefteris. Canadian traveller problem with predictions. In Parinya Chalermsook and Bundit Laekhanukit, editors, Approximation and Online Algorithms, pages 116-133, Cham, 2022. Springer International Publishing. Google Scholar
  16. Richard Bellman. Dynamic programming treatment of the travelling salesman problem. J. ACM, 9(1):61-63, January 1962. Google Scholar
  17. Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Nicole Megow, Leen Stougie, and Michelle Sweering. A universal error measure for input predictions applied to online graph problems. In NeurIPS, 2022. Google Scholar
  18. Antje Bjelde, Jan Hackfeld, Yann Disser, Christoph Hansknecht, Maarten Lipmann, Julie Meißner, Miriam Schlöter, Kevin Schewior, and Leen Stougie. Tight bounds for online TSP on the line. ACM Trans. Algorithms, 17(1):3:1-3:58, 2021. Google Scholar
  19. Michiel Blom, Sven O. Krumke, Willem E. De Paepe, and Leen Stougie. The online TSP against fair adversaries. INFORMS J. Comput., 13(2):138-148, 2001. Google Scholar
  20. Shuchi Chawla and Dimitris Christou. Online time-windows TSP with predictions. CoRR, abs/2304.01958, 2023. URL: https://arxiv.org/abs/2304.01958.
  21. Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In EC, 2021. Google Scholar
  22. Franziska Eberle, Alexander Lindermayr, Nicole Megow, Lukas Nölke, and Jens Schlöter. Robustification of online graph exploration methods. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9):9732-9740, June 2022. Google Scholar
  23. Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In ICML, 2019. Google Scholar
  24. Themistoklis Gouleakis, Konstantinos Lakis, and Golnoosh Shahkarami. Learning-Augmented Algorithms for Online TSP on the Line. In AAAI, 2023. Google Scholar
  25. Michael Held and Richard M. Karp. A dynamic programming approach to sequencing problems. J. Soc. Indust. Appl. Math., 10(1):196-210, 1962. Google Scholar
  26. Hsiao-Yu Hu, Hao-Ting Wei, Meng-Hsi Li, Kai-Min Chung, and Chung-Shou Liao. Online TSP with predictions. CoRR, abs/2206.15364, 2022. URL: https://arxiv.org/abs/2206.15364.
  27. Patrick Jaillet and Michael R. Wagner. Online routing problems: Value of advanced information as improved competitive ratios. Transportation Science, 40:200-210, May 2006. Google Scholar
  28. Vinay A. Jawgal, V. N. Muralidhara, and P. S. Srinivasan. Online travelling salesman problem on a circle. In T.V. Gopal and Junzo Watada, editors, Theory and Applications of Models of Computation, pages 325-336, Cham, 2019. Springer International Publishing. Google Scholar
  29. Murali Kodialam and T. V. Lakshman. Prediction augmented segment routing. In 2021 IEEE 22nd International Conference on High Performance Switching and Routing (HPSR), pages 1-6, 2021. Google Scholar
  30. Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In SIGMOD, 2018. Google Scholar
  31. Eugene L. Lawler, Jan K. Lenstra, Alexander H. G. Rinnooy Kan, and David B. Shmoys. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley Series in Discrete Mathematics & Optimization, 1991. Google Scholar
  32. Alexander Lindermayr and Nicole Megow. Alps. URL: https://algorithms-with-predictions.github.io/.
  33. Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 68(4):24:1-24:25, 2021. URL: https://doi.org/10.1145/3447579.
  34. Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In NeurIPS, 2018. Google Scholar
  35. Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In ITCS, 2020. Google Scholar
  36. Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020. Google Scholar
  37. Benjamin Moseley, Sergei Vassilvitskii, Silvio Lattanzi, and Thomas Lavastida. Online scheduling via learned weights. In SODA, 2020. Google Scholar
  38. Harilaos N. Psaraftis, Marius M. Solomon, Thomas L. Magnanti, and Tai-Up Kim. Routing and scheduling on a shoreline with release times. Manag. Sci., 36(2):212-223, 1990. Google Scholar
  39. Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In NeurIPS, 2018. Google Scholar
  40. Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In SODA, 2020. Google Scholar
  41. Shufan Wang and Jian Li. Online algorithms for multi-shop ski rental with machine learned predictions. In AAMAS, 2020. Google Scholar
  42. Alexander Wei. Better and simpler learning-augmented online caching. In APPROX/RANDOM, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact