Tight Analysis of the Lazy Algorithm for Open Online Dial-a-Ride
SIAM Journal on Discrete Mathematics · 31.03.2026 · 40 (1) · 260-281
DOI: 10.1137/24m1657833 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 09.03.2026. Verfasst von Júlia Baligács und 3 weiteren Autor:innen. Die Arbeit nennt 30 Literaturangaben.
Abstract (Originalsprache)
In the open online dial-a-ride problem, a single server has to deliver transportation requests appearing over time in some metric space, subject to minimizing the completion time. We improve on the best known upper bounds on the competitive ratio on general metric spaces and on the half-line, for both the preemptive and nonpreemptive version of the problem. We achieve this by presenting a new algorithm called [Formula: see text]. More precisely, we show that it has competitive ratio 2.457 on general metric spaces and 2.366 on the half-line. This is the first upper bound that beats known lower bounds of 2.5 for schedule-based algorithms as well as the natural [Formula: see text] algorithm. Furthermore, we provide matching lower bounds on the competitive ratio of [Formula: see text], which yields that our analysis is tight.
Zitieren
APA
Baligács, J., Disser, Y., Mosis, N., & Weckbecker, D. (2026). Tight Analysis of the Lazy Algorithm for Open Online Dial-a-Ride. SIAM Journal on Discrete Mathematics, 40(1), 260-281. https://doi.org/10.1137/24m1657833
Vancouver
Baligács J, Disser Y, Mosis N, Weckbecker D. Tight Analysis of the Lazy Algorithm for Open Online Dial-a-Ride. SIAM Journal on Discrete Mathematics. 2026;40(1):260-281. doi:10.1137/24m1657833
BibTeX
@article{Baligcs2026,
author = {Baligács, Júlia and Disser, Yann and Mosis, Nils and Weckbecker, David},
title = {Tight Analysis of the Lazy Algorithm for Open Online Dial-a-Ride},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {1},
pages = {260--281},
doi = {10.1137/24m1657833}
}
EUVIMED