Skip to main content
The 2024 Developer Survey results are live! See the results
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
7 votes

A Travelling Salesman variant where the next distance depends on distance travelled so far

Without the monotonicity condition, if $f$ is given only by oracle access, then in the worst case you need to query it $\Omega(n!)$ times. Proof sketch: For some sequence of integers $S=[a_1, a_2, \...
Tassle's user avatar
  • 881
5 votes
Accepted

A Travelling Salesman variant where the next distance depends on distance travelled so far

We answer OP's question in the negative. These results are for OP's problem with the monotonicity requirements on $f$ (added in OP's edit after @Tassle's answer, invalidating that answer). Lemma 1. ...
Neal Young's user avatar
  • 10.8k
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,782
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
3 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
2 votes
Accepted

Hardness of the Metric TSP for the Maximum Metric

It is NP-hard, here's a proof. In [1], it is shown that the Hamiltonian path problem is NP-hard on induced subgraphs of the infinite grid (i.e. graphs that are defined by taking a set of integer ...
Laakeri's user avatar
  • 1,831
2 votes

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
  • 121
1 vote

A Travelling Salesman variant where the next distance depends on distance travelled so far

The similarity to Travelling Salesman confused me: the more relevant problem is single-machine scheduling with non-constant job lengths. In particular, this paper surveys many scheduling problems in ...
Erel Segal-Halevi's user avatar
1 vote

Bottom up TSP solution?

"If one takes the 2 nearest neighbors of every node and adds them all up, that is a theoretical minimum." This isn't true. You are adding up 2 edges per vertex, where a TSP solution has one ...
NaturalLogZ'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

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