Tag Info

22

This is a special case of the Travelling Salesman with Neighborhoods (TSPN) problem. In the general version, the neighborhoods need not all be the same. A paper by Dumitrescu and Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, addresses your question. They give a constant factor approximation algorithm for a slightly more general ...

19

Q1. This is a notorious open problem. It is known to be in the fourth level of the counting hierarchy, due to [ABKM]. Not known to be in NP. The problem is not really in computing square roots as claimed in the lecture notes: $n$ bits of a square root of an integer can be computed in time polynomial in $n$ and the bitsize of the integer. The problem is, ...

12

I hope this partly answers your question: Most known heuristics like Greedy, Naerest Neighbor, Lin-Kerninhan etc. perfrom quite well for (symmetric) TSP without triangle inequality. You may check these heuristics with the Concorde TSP Solver which is the best TSP solver I know so far. In theory, there is no heuristic for TSP without triangle inequality ...

10

One relevant TSP version is "Group TSP". In this problem, the "cities" are divided into groups and the goal is to find a tour that visits each group at least once. This has also been studied on the plane, which is closer to what you describe. Here each group is a closed region of the plane and it suffices to visit one point in the region to cover it. See e....

5

The Vehicle Routing Problem was introduced in G. B. Dantzig and J. H. Ramser, The Truck Dispatching Problem, Management Science Vol. 6, No. 1 (Oct., 1959), pp. 80-91. The authors underline the differences with TSP in this way: ... The "truck dispatching problem" formulated in this paper may be considered as a generalization of the TSP ... ... The salesman ...

4

You can also transform the ATSP to TSP; the process requires doubling number of nodes (adding dummy cities). http://www.sciencedirect.com/science/article/pii/0167637783900482 http://www.sciencedirect.com/science/article/pii/0167637786900817

4

You wrote: On the other hand there is this paper by Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 saying it is NP-complete, which also means it is in NP. Although he doesn't prove it in the paper, I think he consider the membership in NP trivial, as is usually the case with such problems. Why don't you simply read the ...

4

This is a special case of the precedence-constrained TSP which has been studied quite a lot. For instance, there are a polyhedral analysis by Balas, Fischetti and Pulleyblank, and a branch-and-cut algorithm by Ascheuer, Jünger and Reinelt.

3

There is no algorithm that runs in time $o(n^2)$ on an $n$-point metric space and returns a tour with weight within a constant factor of the minimum weight: see the argument in Section 9 of this paper by Indyk. On the other hand, if you just want an approximation to the weight of the optimal tour, without actually getting a tour, then you can use this ...

2

In the year 1959, Dantzig and Ramser, the authos of "The truck dispatching problem" described how the Vehicle Routing Problem (VRP) may be considered as a generalization of the Travelling Salesman Problem (TSP). They described the generalization of the TSP with multiple salespeople (supposedly riding a single vehicle each), and called this the “Clover ...

2

This problem is PSPACE-complete even in the case in which the edge weights obey the triangle inequality. See Hsi-Ming Ho, Joel Ouaknine, The Cyclic-Routing UAV Problem is PSPACE-Complete, FoSSaCS 2015

1

Best one I know is the polytime approximation algorithm of Asadpour et al., although maybe this isn't what you want (i.e. you want exact solution, I'm guessing). Anyway, the algorithm achieves $O(\log n / \log \log n)$ approximation for $n$-vertex graphs.

Only top voted, non community-wiki answers of a minimum length are eligible