Hot answers tagged

22 votes
Accepted

What is known about this TSP variant?

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, ...
user avatar
  • 4,493
19 votes
Accepted

Euclidean TSP in NP and square root complexity

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 ...
user avatar
10 votes

What is known about this TSP variant?

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 ...
user avatar
4 votes

Euclidean TSP in NP and square root complexity

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 ...
user avatar
  • 5,712
4 votes

Good algorithms to solve ATSP

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....
user avatar
4 votes
Accepted

Travelling Salesman Problem where a subset of the nodes must be visited in a particular order

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 ...
user avatar
3 votes
Accepted

TSP heuristics for limited distance information

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 ...
user avatar
2 votes

what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)?

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 ...
user avatar
2 votes

TSP with multiple visits

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 ...
user avatar
  • 4,746
1 vote

Good algorithms to solve ATSP

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 ...
user avatar
  • 121

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