跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.26188 · v1

Approximation Algorithms for Asymmetric Multi-Path TSP

首次提交 2026-11-19 22:37
版本更新 2026-11-19 22:37
雷达观测 2026-11-20 14:52
arXiv ↗PDF ↗

摘要

Asymmetric Multi-Path TSP is the generalization of the Asymmetric Traveling Salesperson Problem where we are looking for kk walks, each with prescribed start sis_i and prescribed end tit_i, such that every vertex is visited by at least one of the walks. The objective is to minimize the total length of all walks. In general, it is NP-hard to find any approximation for this problem in polynomial time (even if the approximation factor is allowed to depend on the number of vertices). We show that one can obtain an O(k)O(k)-approximation in time nO(k)n^{O(k)}, answering an open question by Friggstad [2013]. For the special case where all tour start vertices sis_i are identical and all end vertices tit_i are identical, we obtain an O(k)O(k)-approximation in polynomial time, as well as an (O(1ε),1+ε)(O(\frac{1}ε), 1+ε)-bicriteria approximation. For the multi-depot setting, where si=tis_i =t_i for all ii, we obtain a constant-factor approximation in polynomial time. Finally, our results imply improved constant-factor approximation algorithms for Asymmetric Regret-Bounded Vehicle Routing and unit-weight Path ATSP.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-19 22:37 · 最新观测版本

Approximation Algorithms for Asymmetric Multi-Path TSP

Asymmetric Multi-Path TSP is the generalization of the Asymmetric Traveling Salesperson Problem where we are looking for kk walks, each with prescribed start sis_i and prescribed end tit_i, such that every vertex is visited by at least one of the walks. The objective is to minimize the total length of all walks. In general, it is NP-hard to find any approximation for this problem in polynomial time (even if the approximation factor is allowed to depend on the number of vertices). We show that one can obtain an O(k)O(k)-approximation in time nO(k)n^{O(k)}, answering an open question by Friggstad [2013]. For the special case where all tour start vertices sis_i are identical and all end vertices tit_i are identical, we obtain an O(k)O(k)-approximation in polynomial time, as well as an (O(1ε),1+ε)(O(\frac{1}ε), 1+ε)-bicriteria approximation. For the multi-depot setting, where si=tis_i =t_i for all ii, we obtain a constant-factor approximation in polynomial time. Finally, our results imply improved constant-factor approximation algorithms for Asymmetric Regret-Bounded Vehicle Routing and unit-weight Path ATSP.

查看此版本解读 →查看此版本原文 ↗