Tight Bounds for Online TSP on the Line

DOI10.1137/1.9781611974782.63zbMath1415.90096OpenAlexW4213299358MaRDI QIDQ4575803

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

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974782.63

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

New Bounds for Maximizing Revenue in Online Dial-a-Ride ⋮ An improved lower bound for competitive graph exploration ⋮ Unnamed Item ⋮ Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line ⋮ Car-sharing between two locations: online scheduling with flexible advance bookings ⋮ Unnamed Item ⋮ An Improved Online Algorithm for the Traveling Repairperson Problem on a Line ⋮ Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings. ⋮ The online food delivery problem on stars ⋮ Tight competitive analyses of online car-sharing problems

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