Tight analysis of lazy: an improved algorithm for open online dial-a-ride
share
In the open online dial-a-ride problem, a single server has to carry 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, in both, the preemptive and non-preemptive version of the problem. We achieve this by revisiting the algorithm Lazy recently suggested in [WAOA, 2022] and giving an improved and tight analysis. More precisely, we show that it is (3/2+√(11/12) 2.457)-competitive on general metric spaces and (1+1/2(1+√(3))≈ 2.366)-competitive on the half-line.
READ FULL TEXT