DROPS

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

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

Abstract

Cite as

Thanks for your feedback!

Could not send message