Multiple Traveling Salesmen in Asymmetric Metrics

Details Multiple Traveling Salesmen in Asymmetric Metrics Multiple Traveling Salesmen in Asymmetric Metrics

2011-12-13

arxiv.org/abs/1112.2930v2

Computer Science

Data Structures and Algorithms

19 Pages, 3 Figures. First revision fixes a broken reference and adds to the discussion for General 2-ATSPP

Scientific paper

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 (s_1,t_1), ..., (s_k,t_k). The goal is to find an s_i-t_i 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 s_i = t_i 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.

Affiliated with

Also associated with

No associations

Rating

Multiple Traveling Salesmen in Asymmetric Metrics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Multiple Traveling Salesmen in Asymmetric Metrics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple Traveling Salesmen in Asymmetric Metrics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-487210