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.

• Funded by the European Union (ERC, CCOO, 101165139). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.