Por @Alvy — 8 de Julio de 2020
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:
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:
