2026-07-23T08:16:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24934 2025-11-27T06:51:44Z ddc:004 open_access

A Tight Lower Bound for Online Service with Deadlines and Lazy Server Disser, Yann Thelen, Linda online algorithms competitive analysis lower bound delay deadlines 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yann Disser and Linda Thelen 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.26 urn:nbn:de:0030-drops-249347 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.26 eng https://creativecommons.org/licenses/by/4.0/legalcode