36
votes
Accepted
How is the traveling salesman problem verifiable in polynomial time?
NP is the class of problems where you can verify "yes" instances. No guarantee is given that you can verify "no" instances.
The class of problems where you can verify "no" instances in polynomial ...
- 81.4k
30
votes
Accepted
If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?
For 9x9 Sudoku, no. It is finite so can be solved in $O(1)$ time.
But if you had a solver for $n^2 \times n^2$ Sudoku, that worked for all $n$ and all possible partial boards, and ran in polynomial ...
D.W.♦
- 154k
25
votes
If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?
It is indeed possible to use a general Sudoku solver to solve instances of TSP, and if this solver takes polynomial time then the whole process will as well (in complexity terminology, there is a ...
- 510
13
votes
Accepted
Why the need for TSP solvers when there are SAT solvers?
TL;DR: polynomial reduction increases the size of a problem; using a specific solver allows you to exploit the structure of a problem.
When you reduce one NP-complete problem to another one, the size ...
- 887
11
votes
Accepted
Shortest path between two points with n hops
If vertices can be visited more than once, then yes: you can create $n+1$
copies of the graph, with each vertex $v$ in the original graph becoming the $n+1$ vertices $v_1, \dots, v_{n+1}$ and each ...
- 5,439
11
votes
Accepted
Traveling Salesman Solution
First, it's important to recognize the gravity of what you are proposing. If correct, your algorithm is worth $1 Million USD. Secondly, many many people have tried and failed to solve this problem. So ...
- 29.6k
8
votes
Traveling Salesman Problem with Neural Network
there are many papers on using artificial neural networks to solve TSP including recurrent and Hopfield networks, and they "succeed" in a rough sense, but so far there does not seem to be any evidence ...
- 11k
8
votes
Accepted
Why does this not prove $P\neq NP$?
What Fiorini et al. show is the following:
The TSP polytope $P_n$ over $n$ points is a polytope in $\binom{n}{2}$ dimensions whose vertices correspond to all Hamiltonian cycles in $K_n$ (the complete ...
- 274k
8
votes
Accepted
Is there an efficient solution to the travelling salesman problem with binary edge weights?
No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page ...
- 5,439
8
votes
For what applications of the traveling salesman problem, does visiting each city at most once truely matter?
Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not.
In Weighted ...
- 81.4k
7
votes
Accepted
Traveling Salesman Problem with Neural Network
This Medium post lists the latest (not a full list of course) studies in the combinatorial optimization domain. All three papers use Deep Reinforcement Learning, which does not need any training set ...
- 86
7
votes
Accepted
Show that there are $(n-1)!/2$ distinct tours for a Euclidean traveling salesman problem on $n$ points?
We may reason in a combinatorial way.
There are $n!$ permutations of $n$ nodes, but that overcounts the number of tours in two different ways. Since tours are closed, we may start indifferently on ...
- 4,202
6
votes
Accepted
Has it been proven that the optimization TSP is (or is not) polynomial-time verifiable if P ≠ NP?
If $optTSP$ is in $NP$, then $coNP = NP$. The latter is unresolved currently.
Proof: if $optTSP$ is in $NP$, then $coTSP$ is in $coNP$ (the certificate being whatever certificate was provided to ...
- 76
6
votes
Accepted
Why doesn't 2-opt return an optimal solution?
I think I understand now after trying some examples as Yuval Filmus suggested. In the example below, we can get stuck on the local optimum using 2-opt, but as we can see the global optimum is better.
- 685
6
votes
What if the travelling salesman travelled by plane?
I suggest you read more about the Traveling Salesman Problem. All of your questions are answered in other standard references (such as the Wikipedia link I gave). No, the greedy algorithm is not ...
D.W.♦
- 154k
6
votes
Accepted
Why does Travelling Salesman Problem pose the restriction that each vertex can only be visited once?
This mostly comes down to what makes an interesting problem, and what can be easily analyzed.
The restriction of visiting each vertex once is common in these sorts of problems. A traversal that ...
- 7,038
5
votes
Why does this not prove $P\neq NP$?
What you're proposing isn't "a linear program for TSP", so it doesn't come into the scope of the proof.
You've observed that, if $\mathrm{P=NP}$, then TSP can be reduced to polynomial-sized linear ...
- 81.4k
4
votes
Implement multi-fragment heuristics for the traveling salesman problem
there are almost no other information regarding this algorithm online
[...]
I would really appreciate a pseudo-code, if anyone has ever implemented this algorithm.
I invite you to read my paper "...
- 71
4
votes
How to simulate a parallel computer (with certain number of processors) on a serial computer
The Traveling Salesman Problem (TSP) is a classic problem because it's hard to deterministically solve in a decent time frame, classified as NP-hard. Genetic algorithms can get a good solution more ...
- 1,341
4
votes
Why does this graph show the tightness of MST heuristic's 2-approximation bound?
There is a lot of freedom in the algorithm: several minimum spanning trees, and several corresponding Eulerian tours. Try to find the worst choice and show that it produces an inferior tour. What you ...
- 274k
4
votes
Accepted
Travelling Salesman which can repeat cities
I actually found this solution some time ago, but here we go. This is a formulation in a directed graph that can repeat vertices and does not repeat arcs. It requires that for every arc $(i,j)$ there ...
- 201
4
votes
Accepted
Rearranging strings so that the Hamming distance between them is 1
Grid graphs are finite node-induced graphs of the infinite planar grid (whose vertices are integral points, and two vertices are linked when their Euclidean distance is 1). A. Itai, C. H. ...
- 1,173
4
votes
Accepted
How to prove non-existence of $O(2^n)$ approximation algorithm solving TSP?
After @YuvalFilmus' hint it turns out the answer lies in this book. The TSP can be used to solve the Hamiltonian Cycle problem by creating a new graph as following. Given $\alpha > 1$ and a graph $...
- 534
4
votes
Linear Path Optimization with Two Dependent Variables
You can consider the 1D-position of the 2 runners as one 2D-position.
X-coordinate and Y-coordinate for respectively runners 1 and 2. So in your instance, the starting point is (0, 100).
Then all ...
- 1,738
4
votes
Accepted
Standard ILP Formulation of Travelling salesman problem: Purpose of subtour elimination constraints?
Consider this example:
Every vertex has one incoming and one outgoing edge, so it is not prevented by the first two constraints. It is however prevented by the third constraint, as if you take any of ...
- 2,288
4
votes
Accepted
Space complexity of Travelling Salesman Problem
The brute force solution enumerates all permutations. You can easily encode each permutation using $n\log n$ bits, since you can encode it as a list of numbers from $1$ to $n$, and each number takes $\...
- 274k
4
votes
Accepted
Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP
Here is an excerpt from the introduction to an earlier paper of Svensson, Tarnawski and Végh, which was the first to give a constant factor approximation algorithm for ATSP:
Without any assumptions ...
- 274k
4
votes
What is the shortest total path between pairs of points?
This appears to be a maximum matching problem. Well, minimum matching, but you should be able to make the necessary adaptations.
D.W.♦
- 154k
3
votes
Traveling Salesman Problem with Neural Network
I commented this on another answer, but I think it deserves its own answer. Some Google Brain fellows presented a method for solving TSP using an architecture reminiscent of seq2seq in the 2017 paper ...
- 131
3
votes
Accepted
Why does this graph show the tightness of MST heuristic's 2-approximation bound?
The graph I posted is missing some edges, adjacent nodes in the cycle are supposed to be connected. (Edit: Fixed the graph with TSP tour).
The actual graph is this
My solution goes as follows.
Now ...
- 323
Only top scored, non community-wiki answers of a minimum length are eligible