标题： 在线3出租车在一般度量空间上 显示英文标题

标题： Online 3-Taxi on General Metrics

摘要： 在线$k$-出租车问题，由 Fiat、Rabani 和 Ravid 于 1990 年引入，是$k$-服务器问题的推广，其中$k$辆出租车必须在一个度量空间中服务一系列请求。 每个请求是一对两个点，表示乘客的上车和下车地点。 在有趣的“困难”版本中，成本是出租车在没有乘客时行驶的总距离。 这个问题被认为比$k$-服务器问题要困难得多，在此工作之前，甚至对于$k=3$辆出租车，人们还不知道在一般的度量空间上是否可以实现有限的竞争比。 我们提出了一个$O(1)$-竞争算法用于$3$-出租车问题。 显示英文摘要

摘要： The online $k$-taxi problem, introduced in 1990 by Fiat, Rabani and Ravid, is a generalization of the $k$-server problem where $k$ taxis must serve a sequence of requests in a metric space. Each request is a pair of two points, representing the pick-up and drop-off location of a passenger. In the interesting ''hard'' version of the problem, the cost is the total distance that the taxis travel without a passenger. The problem is known to be substantially harder than the $k$-server problem, and prior to this work even for $k=3$ taxis it has been unknown whether a finite competitive ratio is achievable on general metric spaces. We present an $O(1)$-competitive algorithm for the $3$-taxi problem.