Tight Bounds for Online TSP on the Line

DOI10.1145/3422362OpenAlexW3115340459MaRDI QIDQ5028340

Kevin Schewior, Miriam Schlöter, Maarten Lipmann, Julie Meißner, Yann Disser, Antje Bjelde, Jan Hackfeld, Christoph Hansknecht, Leen Stougie

Publication date: 8 February 2022

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-03498401/file/elevator_final.pdf

zbMATH Keywords

TSPcomputational complexitycompetitive analysisonline algorithmsapproximation algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)

Related Items (5)

Online Predictions for Online TSP on the Line ⋮ Tight analysis of the lazy algorithm for open online dial-a-ride ⋮ An improved algorithm for open online dial-a-ride ⋮ Improved bounds for open online dial-a-ride on the line ⋮ Improved bounds for revenue maximization in time-limited online dial-a-ride

This page was built for publication: Tight Bounds for Online TSP on the Line