Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2510.25861 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909877925838848 |
|---|---|
| author | Coester, Christian Poon, Tze-Yang |
| author_facet | Coester, Christian Poon, Tze-Yang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_25861 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Online 3-Taxi on General Metrics Coester, Christian Poon, Tze-Yang Data Structures and Algorithms 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. |
| title | Online 3-Taxi on General Metrics |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.25861 |