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 ...
- 82.2k
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.♦
- 166k
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 ...
- 520
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 ...
- 944
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,509
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 ...
- 30.1k
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 ...
- 279k
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,509
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 ...
- 82.2k
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,272
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.
- 817
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.♦
- 166k
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,176
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 ...
- 82.2k
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
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
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,183
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,351
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,788
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,542
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 $\...
- 279k
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 ...
- 279k
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.♦
- 166k
4
votes
How to prove that this problem is NP Complete
Same class last semester: an edge between two vertices.
Students in a circle: an hamiltonian cycle.
I think you should be able to do the rest.
- 17k
3
votes
Accepted
Traveling Salesman -- number of qubits required?
The notebook describes how to solve combinatorial optimization problems by encoding them as minimizing a binary quadratic form, which can in turn be phrased as finding the minimal eigenvalue of a ...
- 279k
3
votes
Is a two-opt move guaranteed to produce a non-worse tour?
2-Opt is a move that doesn't guarantee to give a better tour.
We use such moves ($k$-Opt, swap, insertion,..) in local searches to look for a better tour in the neighbor of the input (which is a tour)...
- 71
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
Traveling salesman problem with disconnected cities / infinite length edge
You're just trying to find Hamiltonian cycles in unweighted graphs. That's still NP-complete.
If you want to do it with a TSP solver, do it as follows. Suppose you have a graph on $n$ vertices. ...
- 82.2k
3
votes
Accepted
Travelling salesman problem with small edge weights
Travelling salesman remains NP-complete even if you restrict to two different edge weights $a<b$. Reduce from Hamiltonian cycle by giving weight $a$ to every edge and weight $b$ to every ...
- 82.2k
Only top scored, non community-wiki answers of a minimum length are eligible