Online 3-Taxi on General Metrics

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.