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 + \varphi \approx 2.618$ for some choice of its parameter, where $\varphi$ 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.
翻译：我们考虑了开放的在线拨号车道问题,在这种问题上,运输请求以一个公尺空间出现在网上,需要由一个服务器提供服务。目标是在所有请求都得到满足之前尽可能缩短完成时间。我们为此问题提出了一个新的参数化算法,并证明它在某些参数选择方面达到了1美元+\varphi\ approx 2.618美元的竞争比率,其中,$\varphie是黄金比率。这改善了已知的开放在线拨号车的界限,既包括普通的计量空间,也包括实际线路。我们还为我们任何参数选择的竞争性算法提供了2 457美元的较低界限。
相关内容
微信扫码咨询专知VIP会员