En general, para cualquier "c" > 0, donde "d" es el número de dimensiones en el espacio Euclidiano, existe un algoritmo polinomial que encuentra un camino de longitud a lo sumo (1 + 1/"c"), el óptimo para instancia geométricas del TSP se da en tiempo formula_38; este es llamado un esquema de aproximación a tiempo polinomial (PTAS por sus siglas en inglés).