← 研踪 PaperTrailarXiv:2611.21943 · v1
Beyond 4: Improved Competitive Traveling Repairperson
首次提交 2026-11-17 06:07
版本更新 2026-11-17 06:07
雷达观测 2026-11-18 19:43
摘要
With repairpersons starting initially from a depot, we present a 3.877-competitive deterministic algorithm for the fundamental online traveling repairperson problem on an arbitrary metric. For the special class of zero-residual instances, we improve the ratio to for every . We also extend these results to some variants of the related so-called online dial-a-ride problem. The state-of-the-art is the 4-competitive deterministic algorithm for both problems.
作者备注:27 pages, 1 figure, 2 pseudocodes, 1 table
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-17 06:07 · 最新观测版本
Beyond 4: Improved Competitive Traveling Repairperson
With repairpersons starting initially from a depot, we present a 3.877-competitive deterministic algorithm for the fundamental online traveling repairperson problem on an arbitrary metric. For the special class of zero-residual instances, we improve the ratio to for every . We also extend these results to some variants of the related so-called online dial-a-ride problem. The state-of-the-art is the 4-competitive deterministic algorithm for both problems.
查看此版本解读 →查看此版本原文 ↗