Online TSP and Online Dial-a-Ride with Predictions

References

• Angelopoulos A, Dürr C, Jin S, Kamali S, Renault M (2020) Online computation with untrusted advice. 11th Innovations Theoretical Comput. Sci. Conf. (ITCS 2020), 151:52:1–52:15.Google Scholar
• Antoniadis A, Gouleakis T, Kleer P, Kolev P (2020) Secretary and online matching problems with machine learned advice. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Adv. Neural Inform. Proc. Systems (NeurIPS), vol. 33 (Curran Associates, Inc., Red Hook, NY), 7933–7944.Google Scholar
• Ascheuer N, Krumke SO, Rambau J (2000) Online dial-a-ride problems: Minimizing the completion time. Reichel H, Tison S, eds. Stacs 2000 (Springer Berlin Heidelberg, Berlin, Heidelberg), 639–650.Crossref, Google Scholar
• Ausiello G, Feuerstein E, Leonardi S, Stougie L, Talamo M (2001) Algorithms for the on-line travelling salesman. Algorithmica 29(4):560–581.Crossref, Google Scholar
• Azar Y, Panigrahi D, Touitou N (2022) Online graph algorithms with predictions. Proc. 2022 Annual ACM-SIAM Symposium Discrete Algorithms (SODA) (ACM, New York), 35–66.Google Scholar
• Balkanski E, Ou T, Stein C, Wei H-T (2023) Scheduling with speed predictions. International Workshop on Approximation and Online Algorithms (WAOA) (Springer, New York).Crossref, Google Scholar
• Bamas E, Maggiori A, Rohwedder L, Svensson O (2020) Learning augmented energy minimization via speed scaling. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Adv. Neural Inform. Proc. Systems (NeurIPS), vol. 33 (Curran Associates, Inc., Red Hook, NY), 15350–15359.Google Scholar
• Bamas E, Maggiori A, Svensson O (2020) The primal-dual method for learning augmented algorithms. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Adv. Neural Inform. Proc. Systems (NeurIPS), vol. 33 (Curran Associates, Inc., Red Hook, NY), 20083–20094.Google Scholar
• Bampis E, Escoffier B, Gouleakis T, Hahn N, Lakis K, Shahkarami G, Xefteris M (2023) Learning-augmented online TSP on rings, trees, flowers and (almost) everywhere else. 31st Annual Eur. Symposium Algorithms, ESA 2023, September 4–6, 2023, Amsterdam, Netherlands, vol. 274, 12:1–12:17.Google Scholar
• Banerjee S, Cohen-Addad V, Gupta A, Li Z (2023) Graph searching with predictions. 14th Innovations Theoretical Comput. Sci. Conf. (ITCS 2023), vol. 251, 12:1–12:24.Google Scholar
• Bernardini G, Lindermayr A, Marchetti-Spaccamela A, Megow N, Stougie L, Sweering M (2022) A universal error measure for input predictions applied to online graph problems. Adv. Neural Inform. Proc. Systems (NeurIPS) (Curran Associates, Inc., Red Hook, NY).Google Scholar
• Bjelde A, Hackfeld J, Disser Y, Hansknecht C, Lipmann M, Meißner J, Schlöter M, Schewior K, Stougie L (2021) Tight bounds for online TSP on the line. ACM Trans. Algorithms 17(1):1–58.Crossref, Google Scholar
• Blum A (1998) On-line algorithms in machine learning. Fiat A, Woeginger GJ, eds. Online Algorithms: The State of the Art (Springer Nature, New York), 306–325.Crossref, Google Scholar
• Chawla S, Christou D (2024) Online time-windows TSP with predictions. Kumar A, Ron-Zewi N, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024), Leibniz International Proceedings in Informatics (LIPIcs), vol. 317 (Schloss Dagstuhl – Leibniz-Zentrum f¨ur Informatik, Dagstuhl, Germany), 2:1–2:21.Google Scholar
• Chen J, Silwal S, Vakilian A, Zhang F (2022) Faster fundamental graph algorithms via learned predictions. Internat. Conf. Machine Learning (PMLR, New York), 3583–3602.Google Scholar
• Dütting P, Lattanzi S, Paes Leme R, Vassilvitskii S (2021) Secretaries with advice. Proc. 22nd ACM Conf. Econom. Comput. EC ‘21 (Association for Computing Machinery, Budapest, Hungary), 409–429.Google Scholar
• Fotakis F, Gergatsouli E, Gouleakis T, Patris N (2021) Learning augmented online facility location. Preprint, submitted July 17, https://arxiv.org/abs/2107.08277.Google Scholar
• Fujii K, Yoshida Y (2023) The secretary problem with predictions. Math. Oper. Res. 49(2):1241–1262.Link, Google Scholar
• Gouleakis T, Lakis K, Shahkarami G (2023) Learning-augmented algorithms for online TSP on the line. AAAI 37(10):11989–11996.Crossref, Google Scholar
• Im S, Kumar R, Montazer Qaem M, Purohit M (2021) Online knapsack with frequency predictions. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. Adv. Neural Inform. Proc. Systems (NeurIPS), vol. 34 (Curran Associates, Inc., Red Hook, NY), 2733–2743.Google Scholar
• Lattanzi S, Lavastida T, Moseley B, Vassilvitskii S (2020) Online scheduling via learned weights. Proc. 2020 ACM-SIAM Symposium Discrete Algorithms (SODA), 1859–1877.Google Scholar
• Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (1985) The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization (Wiley, Hoboken, NJ).Google Scholar
• Lykouris T, Vassilvitskii S (2021) Competitive caching with machine learned advice. J. ACM 68(4):1–25.Crossref, Google Scholar
• Mitzenmacher M (2021) Queues with small advice. Proc. 2021 SIAM Conf. Applied Comput. Discrete Algorithms (ACDA21) (SIAM, Philadelphia, PA), 1–12.Google Scholar
• Munoz A, Vassilvitskii S (2017) Revenue optimization with approximate bid predictions. Guyon I, ed. Adv. Neural Inform. Proc. Systems (NeurIPS) (Curran Associates, Inc., Red Hook, NY).Google Scholar
• Purohit M, Svitkina Z, Kumar R (2018) Improving online algorithms via ML predictions. Bengio S, ed. Adv. Neural Inform. Proc. Systems (NeurIPS), vol. 31 (Curran Associates, Inc., Red Hook, NY).Google Scholar
• Rohatgi D (2020) Near-optimal bounds for online caching with machine learned advice. Proc. 2020 ACM-SIAM Symposium Discrete Algorithms (SODA) (ACM, New York), 1834–1845.Google Scholar
• Stein C, Wei H-T (2023) Learning-augmented online packet scheduling with deadlines. Preprint, submitted May 11, https://arxiv.org/abs/2305.07164.Google Scholar
• Wei H-T (2024) Scheduling and routing under uncertainty with predictions. PhD thesis, Columbia University, New York.Google Scholar
• Wei A, Zhang F (2020) Optimal robustness-consistency trade-offs for learning-augmented online algorithms. Larochelle H, ed. Adv. Neural Inform. Proc. Systems (NeurIPS), vol. 33 (Curran Associates, Inc., Red Hook, NY), 8042–8053.Google Scholar
• Xu C, Moseley B (2022) Learning-augmented algorithms for online Steiner tree. AAAI 36(8):8744–8752.Crossref, Google Scholar