{"ID":2848729,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.25861","arxiv_id":"2510.25861","title":"Online 3-Taxi on General Metrics","abstract":"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.","short_abstract":"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'' v...","url_abs":"https://arxiv.org/abs/2510.25861","url_pdf":"https://arxiv.org/pdf/2510.25861v1","authors":"[\"Christian Coester\",\"Tze-Yang Poon\"]","published":"2025-10-29T18:04:14Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}