All Questions
Tagged with exp-time-algorithms tsp
3 questions
18
votes
3
answers
1k
views
Solving Superstring Exactly
What is known about exact complexity of the shortest superstring problem? Can it be solved faster than $O^*(2^n)$? Are there known algorithms that solve shortest superstring without reducing to TSP?
...
- 2,257
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,257
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