Approximation algorithms for Euclidean Traveling Salesman
Euclidean TSP is not even known to be in $NP$, basically because it seems that even to verify if there is a hamiltonian cycle of length at most $k$, we need to computing the sum of square roots. But the problem "$\sum_{i}\sqrt{a_i}&lt;k?$" is not known to be in $NP$.

Anyway Euclidean TSP has $PTAS$.