论文标题
对开放式在线拨号的懒惰算法的严格分析
Tight analysis of the lazy algorithm for open online dial-a-ride
论文作者
论文摘要
在开放的在线拨号问题中，单个服务器必须在某些度量空间中随着时间的推移出现的运输请求提供，但要减少完成时间。我们在一般度量空间和半行的竞争比率上提高了最著名的上限，这是该问题的抢先和非抢先版本。我们通过重新访问[WAOA，2022]中建议的算法$ \ textsc {lazy} $来实现这一目标，并进行了改进而紧密的分析。更确切地说，我们表明，它的竞争比率为2.457美元，一般度量的$ 2.457 $，半行的$ 2.366 $。这是对基于时间表的算法以及天然$ \ textsc {replan} $算法的第一个上界，它比计划基于计划的算法的2.5的下限。
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 non-preemptive version of the problem. We achieve this by revisiting the algorithm $\textsc{Lazy}$ recently suggested in [WAOA, 2022] and giving an improved and tight analysis. 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 $\textsc{Replan}$ algorithm.
