Hot answers tagged

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 ...
Sasho Nikolov's 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 ...
Thomas Kalinowski's user avatar
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....
Edward Kirton's 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 ...
Gamow's user avatar
  • 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 ...
Alfonso F R's user avatar
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 ...
NaturalLogZ's user avatar
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 ...
dimathe47's user avatar
  • 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$, ...
Ferazhu's user avatar
  • 11

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