← 研踪 PaperTrailarXiv: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
摘要
Asymmetric Multi-Path TSP is the generalization of the Asymmetric Traveling Salesperson Problem where we are looking for walks, each with prescribed start and prescribed end , 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 -approximation in time , answering an open question by Friggstad [2013]. For the special case where all tour start vertices are identical and all end vertices are identical, we obtain an -approximation in polynomial time, as well as an -bicriteria approximation. For the multi-depot setting, where for all , 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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 walks, each with prescribed start and prescribed end , 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 -approximation in time , answering an open question by Friggstad [2013]. For the special case where all tour start vertices are identical and all end vertices are identical, we obtain an -approximation in polynomial time, as well as an -bicriteria approximation. For the multi-depot setting, where for all , 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.
查看此版本解读 →查看此版本原文 ↗