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 ...
user avatar
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 ...
user avatar
  • 141k
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 ...
user avatar
  • 510
16 votes
Accepted

What is the optimal solution of the 1962 Procter and Gamble's TSP Contest?

Full details are in Robert L. Karg and James L. Thompson, A Heuristic Approach to Solving Traveling Salesman Problems (Management Science, 10(2):225–248, 1964). The PDF is available from JStor ...
user avatar
12 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 29.1k
8 votes
Accepted

Minimum distance between start and end by going through must visit points in a maze

Most real mazes are trees and there is a polynomial time algorithm for this problem on trees. For ease of description, orient all edges of the tree to point away from the start vertex. Now, for each ...
user avatar
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 ...
user avatar
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 ...
user avatar
7 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 ...
user avatar
  • 10.8k
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 ...
user avatar
  • 4,132
7 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 ...
user avatar
6 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 ...
user avatar
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 ...
user avatar
  • 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.
user avatar
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 ...
user avatar
  • 141k
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 ...
user avatar
  • 6,940
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 ...
user avatar
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 ...
user avatar
4 votes

Travelling Salesman which can repeat cities

This is directly equivalent to metric TSP. That is, TSP in which the distances obey the triangle inequality: for all cities $A$, $B$ and $C$, the distance from $A$ to $B$ is no greater than ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 1,331
4 votes
Accepted

Is the Euclidean TSP weakly NP-hard?

You're confusing a polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS). Euclidean TSP has a PTAS, but it is not an FPTAS because the polynomial ...
user avatar
  • 7,843
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 "...
user avatar
  • 71
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. ...
user avatar
  • 1,163
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 $...
user avatar
  • 524
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 ...
user avatar
  • 1,730
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 ...
user avatar
  • 2,209
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 $\...
user avatar

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