The Online k-Taxi Problem Is Competitive on All Metrics

The online k-taxi problem is a natural generalization of the k-server problem: k taxis must serve a sequence of requests in a metric space. Each request is a pair of points $(r,s)$, and the algorithm serves the request by first moving a taxi to r (to pick up a passenger) and then to s (to drop off the passenger). The cost is the total distance traveled by the taxis without a passenger. Previous bounds for general k all depended on the number of points n or the aspect ratio $Δ$ of the metric space, both of which can be infinite on general metrics, and competitive algorithms were previously known on general metrics only for k ≤ 3. In this work, we give a 9ᵏ⁻¹-competitive randomized algorithm against adaptive online adversaries and, as a corollary, an 81ᵏ⁻¹-competitive deterministic algorithm for the online k-taxi problem.