论文标题
改进的算法，用于开放在线拨号拨号
An Improved Algorithm for Open Online Dial-a-Ride
论文作者
论文摘要
我们考虑开放的在线拨号问题，其中运输请求在公制空间中在线出现，需要由单个服务器提供。目的是将完成时间最小化，直到满足所有请求为止。我们为此问题提供了一种新的，参数化的算法，并证明其达到$ 1 +φ\ $ 1 +φ\约2.618 $的竞争比率，其中某种选择的参数为$φ$是黄金比率。这改善了通用度量空间以及真实线路的开放式在线拨号的最著名界限。对于任何参数选择，我们还为算法的竞争比率提供了约2.457美元的$ 2.457 $。
We consider the open online dial-a-ride problem, where transportation requests appear online in a metric space and need to be served by a single server. The objective is to minimize the completion time until all requests have been served. We present a new, parameterized algorithm for this problem and prove that it attains a competitive ratio of $1 + φ\approx 2.618$ for some choice of its parameter, where $φ$ is the golden ratio. This improves the best known bounds for open online dial-a-ride both for general metric spaces as well as for the real line. We also give a lower bound of~$2.457$ for the competitive ratio of our algorithm for any parameter choice.
