← 研踪 PaperTrailarXiv:2611.24385 · v1
Improved Bounds for Online TSP on the Half-Line
首次提交 2026-11-18 21:15
版本更新 2026-11-18 21:15
雷达观测 2026-11-19 15:04
摘要
In the open online traveling salesperson problem, requests appear over time at different positions of a metric space. A single agent traveling at unit speed must serve all requests, by visiting their positions, with the objective of minimizing the completion time. We propose online algorithms for this problem for the case that the metric space is the half-line. First, we present a -competitive algorithm in which the server always either moves at unit speed or remains stationary, which improves on the previously best-known ratio of . We further observe that algorithms must sometimes move slower than unit speed to achieve competitive ratios below . We introduce a second algorithm that beats the barrier of by carefully modulating its speed, and prove a tight bound of on its competitive ratio. Finally, we slightly strengthen a known lower bound on the best-possible competitive ratio on the half-line from to .
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-18 21:15 · 最新观测版本
Improved Bounds for Online TSP on the Half-Line
In the open online traveling salesperson problem, requests appear over time at different positions of a metric space. A single agent traveling at unit speed must serve all requests, by visiting their positions, with the objective of minimizing the completion time. We propose online algorithms for this problem for the case that the metric space is the half-line. First, we present a -competitive algorithm in which the server always either moves at unit speed or remains stationary, which improves on the previously best-known ratio of . We further observe that algorithms must sometimes move slower than unit speed to achieve competitive ratios below . We introduce a second algorithm that beats the barrier of by carefully modulating its speed, and prove a tight bound of on its competitive ratio. Finally, we slightly strengthen a known lower bound on the best-possible competitive ratio on the half-line from to .
查看此版本解读 →查看此版本原文 ↗