DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2026.4

Improved Bounds for Online TSP on the Half-Line

Authors: Júlia Baligács, Yann Disser, and Linda Thelen

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract

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.

Cite as

Júlia Baligács, Yann Disser, and Linda Thelen. Improved Bounds for Online TSP on the Half-Line. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{baligacs_et_al:LIPIcs.SWAT.2026.4,
  author =	{Balig\'{a}cs, J\'{u}lia and Disser, Yann and Thelen, Linda},
  title =	{{Improved Bounds for Online TSP on the Half-Line}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.4},
  URN =		{urn:nbn:de:0030-drops-260402},
  doi =		{10.4230/LIPIcs.SWAT.2026.4},
  annote =	{Keywords: online algorithms, competitive analysis, server problems, online TSP}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.26

A Tight Lower Bound for Online Service with Deadlines and Lazy Server

Authors: Yann Disser and Linda Thelen

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

We study the online service with deadlines (or delays) problem, in which a server must serve requests for points in a metric space while balancing travel distance and promptness of service. While the problem has been extensively studied (STOC 2017), (FOCS 2019), (FOCS 2023), the main open question whether a constant competitive ratio can be achieved remains wide open. We prove a logarithmic lower bound for a natural class of algorithms already on uniform line metrics. Our lower bound applies to, and is tight for, the best known algorithms for general metrics and uniform line metrics.

Cite as

Yann Disser and Linda Thelen. A Tight Lower Bound for Online Service with Deadlines and Lazy Server. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{disser_et_al:LIPIcs.ISAAC.2025.26,
  author =	{Disser, Yann and Thelen, Linda},
  title =	{{A Tight Lower Bound for Online Service with Deadlines and Lazy Server}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.26},
  URN =		{urn:nbn:de:0030-drops-249347},
  doi =		{10.4230/LIPIcs.ISAAC.2025.26},
  annote =	{Keywords: online algorithms, competitive analysis, lower bound, delay, deadlines}
}

Search Results

Documents authored by Thelen, Linda

Improved Bounds for Online TSP on the Half-Line

Abstract

Cite as

A Tight Lower Bound for Online Service with Deadlines and Lazy Server

Abstract

Cite as

Thanks for your feedback!

Could not send message