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 ...
- 18.1k
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 ...
- 1,026
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....
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 ...
- 5,772
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 ...
- 27
1
vote
What is known about (upper bounds on) the LP gap of the (symmetric) Travelling salesman in special instances?
Are you asking about lower or upper bounds on the integrality gap? For lower bounds, we know that the gap is at least 4/3. That example that shows this is planar, graphic, and Euclidean (well each of ...
- 226
1
vote
Time complexity of Held-Karp algorithm for TSP
Main note
It's important to note that we compute and store not
"distance of optimal path for combination of k cities"
but
"distance of optimal path ...
- 111
1
vote
Generate TSP instances with known optimal
If someone is still searching for this, I might give a gist of how I understood that paper:
Generate an optimal permutation $p$ of $\{1...n\}$.
Create two random variables, $\alpha_i$ and $\beta_j$, ...
- 11
Only top scored, non community-wiki answers of a minimum length are eligible