Metraipolis › archive › dc_d3c0107259cd
The Online $k$-Taxi Problem Is Competitive on All Metrics — arXiv:2611.06684
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06684
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:31:42.231Z
- SHA-256 of the archived text
1c887ca48603dd9b77f377ca75f7e1f54a694be96fa33c4ea5456aa49c6a9b2a- Stable URL of this page
https://metraipolis.com/documento/dc_d3c0107259cd
How to cite
The Online $k$-Taxi Problem Is Competitive on All Metrics — arXiv:2611.06684 — arXiv (en), https://arxiv.org/abs/2611.06684 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d3c0107259cd (Metraipolis archive dc_d3c0107259cd, sha256 1c887ca48603dd9b77f377ca75f7e1f54a694be96fa33c4ea5456aa49c6a9b2a)
BibTeX
@misc{dcd3c0107259cd,
title = {The Online $k$-Taxi Problem Is Competitive on All Metrics — arXiv:2611.06684},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06684},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d3c0107259cd; sha256 1c887ca48603dd9b77f377ca75f7e1f54a694be96fa33c4ea5456aa49c6a9b2a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06684. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\Delta$ 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 \le 3$. In this work, we give a $9^{k-1}$-competitive randomized algorithm against adaptive online adversaries and, as a corollary, an $81^{k-1}$-competitive deterministic algorithm for the online $k$-taxi problem.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.06684 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:21:04.031Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).