HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is the Euclidean TSP weakly NP-hard?

Submitted by: @import:stackexchange-cs··
0
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?

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.