Metric TSP con costo de arista entero

Question

Dado un TSP métrico con costos de borde enteros acotados superiormente por una constante $C_{\max}$, ¿podemos encontrar un algoritmo polinómico que resuelva esta instancia de TSP?

Answer 1

No existe un algoritmo de tiempo polinomial, a menos que P = NP.

De hecho, incluso para instancias de TSP donde todas las distancias son $1$ o $2$ (nota que automáticamente satisfacen la desigualdad triangular), Engebretsen y Karpinski mostraron que es NP-hard aproximarse a TSP dentro de un factor de $\frac{741}{740} - \epsilon$, para cualquier $\epsilon > 0$.