← 研踪 PaperTrailarXiv:2611.06684 · v1
The Online $k$-Taxi Problem Is Competitive on All Metrics
首次提交 2026-11-04 23:52
版本更新 2026-11-04 23:52
雷达观测 2026-11-05 12:13
摘要
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 \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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-04 23:52 · 最新观测版本
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 \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.
查看此版本解读 →查看此版本原文 ↗