3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ see also Why we can't have FPTAS for strong NP complete problems $\endgroup$ – vzn Apr 30 '15 at 18:15
  • $\begingroup$ Why would it be a contradiction? "Strongly NP-hard" is not the same concept as "NP-hard". $\endgroup$ – D.W.♦ Apr 30 '15 at 21:11
  • $\begingroup$ @D.W. Of course it is not. I just wanted to know where the failure in my understanding was. Maybe the question is not optimally formulated. $\endgroup$ – surt91 May 1 '15 at 15:39
  • $\begingroup$ You could have PTAS for Strongly NP-hard Problem!!! But you cannot have FPTAS for Strongly NP-hard problem unless P=NP $\endgroup$ – user777 Mar 1 '18 at 10:09
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ feel something is missing here. has euclidean TSP been proven strongly NP hard? $\endgroup$ – vzn Apr 30 '15 at 18:17
  • $\begingroup$ @vzn [Papadimitriou 1977] show that Euclidean TSP is NP-complete. The reduction from Exact Cover by 3-Sets problem (this problem is known to be as another way of 3-Dimentional Matching problem which has reduction from 3-SAT, all these problems are known to be NP-hard in the strong sense "hard for even small number" so this implies that Euclidean TSP is NP-hard in the strong sense). [sciencedirect.com/science/article/pii/0304397577900123/… $\endgroup$ – user777 Mar 1 '18 at 10:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.