2026-07-21T03:04:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26040 2026-06-23T13:18:29Z ddc:004 open_access

Improved Bounds for Online TSP on the Half-Line Baligács, Júlia Disser, Yann Thelen, Linda online algorithms competitive analysis server problems online TSP In the open online traveling salesperson problem, requests appear over time at different positions of a metric space. A single agent traveling at unit speed must serve all requests, by visiting their positions, with the objective of minimizing the completion time. We propose online algorithms for this problem for the case that the metric space is the half-line. First, we present a 2-competitive algorithm in which the server always either moves at unit speed or remains stationary, which improves on the previously best-known ratio of 2.04. We further observe that algorithms must sometimes move slower than unit speed to achieve competitive ratios below 2. We introduce a second algorithm that beats the barrier of 2 by carefully modulating its speed, and prove a tight bound of 1.75 on its competitive ratio. Finally, we slightly strengthen a known lower bound on the best-possible competitive ratio on the half-line from 1.627 to 1.646. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Júlia Baligács and Yann Disser and Linda Thelen 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.4 urn:nbn:de:0030-drops-260402 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.4 eng https://creativecommons.org/licenses/by/4.0/legalcode