Online 3-taxi on general metrics

Conference item

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.

Authors: Coester, C; Poon, T-Y

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Host title: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
• Pages: 6659 - 6673
• Publication date: 2026-01-07
• Acceptance date: 2025-10-03
• Event title: ACM-SIAM Symposium on Discrete Algorithms (SODA 2026)
• Event location: Vancouver, Canada
• Event website: https://www.siam.org/conferences-events/siam-conferences/soda26/
• Event start date: 2026-01-11
• Event end date: 2026-01-14
• DOI: 10.1137/1.9781611978971.238
• EISBN: 9781611978971
• Language: English