patternMinor
Is the Euclidean TSP weakly NP-hard?
Viewed 0 times
tsptheweaklyhardeuclidean
Problem
So the Euclidean TSP decision problem is NP-complete (see http://dx.doi.org/10.1016/0304-3975(77)90012-3 ) so the TSP optimization problem should be NP-hard.
On the other hand there is a PTAS for the Euclidean TSP (see http://dx.doi.org/10.1145/290179.290180 ).
Wikipedia says that a PTAS is not possible for strongly NP-hard Problems.
So is this a contradiction, or is the Euclidean TSP "only" weakly NP-hard?
Did I miss something else?
On the other hand there is a PTAS for the Euclidean TSP (see http://dx.doi.org/10.1145/290179.290180 ).
Wikipedia says that a PTAS is not possible for strongly NP-hard Problems.
So is this a contradiction, or is the Euclidean TSP "only" weakly NP-hard?
Did I miss something else?
Solution
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 increases in degree as 1 / ε decreases. Only an FPTAS is disallowed for strongly NP-hard problems, assuming P $\neq$ NP.
Context
StackExchange Computer Science Q#42001, answer score: 4
Revisions (0)
No revisions yet.