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 $(\frac{3}{2}+\sqrt{11/12}\thickapprox 2.457)$-competitive on general metric spaces and $(1+\frac{1}{2}(1+\sqrt{3})\approx 2.366)$-competitive on the half-line.
翻译：在开放在线拨号上的问题中,单个服务器必须随时间推移一些公制空间出现的运输请求,但需尽量减少完成时间。我们改进了一般公制空间竞争比率和半线上最知名的上限,既有先发制人版,也有非先发制人版的问题。我们通过重新审查[WAOA, 2022] 中最近建议的Lazy算法并改进和严格分析来做到这一点。更准确地说,我们显示,一般公制公制空间的竞争力为$(frac{3 ⁇ 2 ⁇ 2 ⁇ sqrt{11/12 ⁇ thickapprox 2.457),而普通公制空间的竞争力为$(1 ⁇ frac{1 ⁇ 2}(1 ⁇ sqrt{3})\约2.3666美元。
相关内容
微信扫码咨询专知VIP会员