2011/12/13 by Zachary Friggstad, Friggstad, Zachary · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Connection (principal bundle) #Data Structures and Algorithms (cs.DS) #Discrete mathematics #F.2.2 #FOS: Computer and information sciences #Geometry #Integer (computer science) #Linear programming #Linear programming relaxation #Mathematical optimization #Mathematics #Metric (unit) #Optimization and Search Problems #Path (computing) #Relaxation (psychology) #Travelling salesman problem #cs.DS
paper · pdf · doi:10.48550/arxiv.1112.2930
published in arXiv (Cornell University) (Cornell University) · 19 Pages, 3 Figures. First revision fixes a broken reference and adds to the discussion for General 2-ATSPP
openalex publication_date 2011/12/13 · arxiv created 2011/12/14 · arxiv updated 2011/12/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
We consider some generalizations of the Asymmetric Traveling Salesman Path problem. Suppose we have an asymmetric metric G = (V,A) with two distinguished nodes s,t. We are also given a positive integer k. The goal is to find k paths of minimum total cost from s to t whose union spans all nodes. We call this the k-Person Asymmetric Traveling Salesmen Path problem (k-ATSPP). Our main result for k-ATSPP is a bicriteria approximation that, for some parameter b >= 1 we may choose, finds between k and k + k/b paths of total length O(b log |V|) times the optimum value of an LP relaxation based on the Held-Karp relaxation for the Traveling Salesman problem. On one extreme this is an O(log |V|)-approximation that uses up to 2k paths and on the other it is an O(k log |V|)-approximation that uses exactly k paths. Next, we consider the case where we have k pairs of nodes (s1,t1), ..., (sk,tk). The goal is to find an si-ti path for every pair such that each node of G lies on at least one of these paths. Simple approximation algorithms are presented for the special cases where the metric is symmetric or where si = ti for each i. We also show that the problem can be approximated within a factor O(log n) when k=2. On the other hand, we demonstrate that the general problem cannot be approximated within any bounded ratio unless P = NP.