Questions tagged [tsp]
The travelling salesman problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.
8
questions
21
votes
4
answers
2k
views
DNA-algorithms and NP-completeness
What is the relationship between DNA-algorithms and the complexity classes defined using Turing machines? What do the complexity measures like time and space correspond to in DNA-algorithms? Can they ...
- 283
46
votes
4
answers
14k
views
Approximation algorithms for Metric TSP
It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time.
Is anything known about finding approximation solutions in ...
- 2,247
9
votes
2
answers
1k
views
Generating interesting combinatorial optimization problems
I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$...
- 193
12
votes
2
answers
869
views
Euclidean TSP in NP and square root complexity
In this lecture notes by Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf, it is said that we don't know if Euclidean TSP is in NP:
The reason being that we do not ...
- 363
9
votes
2
answers
7k
views
Time complexity of Held-Karp algorithm for TSP
When I looked through "A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp1, I came up with the following question:
why the complexity of their ...
- 4,215
6
votes
3
answers
2k
views
A simple approximation algorithm for the TSP
Consider the following extremely simple approximation algorithm for the TSP.
Input: A complete weighted graph $G=(V,E).$
Take any three vertices $a,b,c\in V$ and let $H:=(a,b,c,a).$
While there ...
- 338
5
votes
1
answer
2k
views
Approximation for metric TSP: Worst case using nearest neighbor heuristic?
I'm looking at different heuristics that approximate solutions for a metric Traveling Salesman Problem. I was wondering if there is a worst case ratio of tours calculated by the nearest neighbor ...
- 153
4
votes
1
answer
1k
views
Heuristics for tsp without triangle inequality
Every heuristic for the traveling salesman problem that I know of (Nearest-Neighbour, Christofides, Held-Karp, ...) assumes that the triangle inequality holds.
Are there heuristics to solve the tsp ...
- 227