Anna Karlin, Nathan Klein y Shayan Gharan de la Universidad de Washington han publicado un trabajo en el que se mejora más allá de 3/2 el ratio de aproximación a la mejor solución conocida hasta ahora para el problema del viajante, un clásico de la combinatoria y la complejidad computacional:

Dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que puede seguir un viajante para visitar cada ciudad exactamente una vez y regresando al finalizar a la ciudad origen?

El trabajo completo se puede descargar de ArXiv:

A (Slightly) Improved Approximation Algorithm for Metric Travelling Saleman Problem (TSP) [PDF]

Según cuenta Reza Zadeh, que es donde vi el aviso, la ratio de 3/2 databa ni más ni menos que de 1976, porque no había habido grandes avances desde entonces: hace 44 años. Combina varias técnicas que no siendo matemático no me atrevo ni a mencionar. Como bien dice Zadeh, «el resumen de la demostración tiene una sola línea, pero el trabajo en sí son 85 páginas»

Relacionado:

Una forma de resolver el problema del viajante, visualmente explicada
La ameba que resuelve el «problema del viajante» con cierta habilidad
Travelling Salesman, trailer. (O qué sucedería si P=NP)

# Enlace Permanente