Por @Alvy — 8 de Julio de 2020

Avances y mejoras en la solución al problema matemático del viajante

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:

Compartir en Flipboard Compartir en Facebook Tuitear

PUBLICIDAD




PUBLICIDAD


Microsiervos Selección


A New Kind of Science

EUR 9,43

Comprar


Foolproof, and Other Mathematical Meditations

EUR 12,74

Comprar


Amazon Associates

Los productos aquí enlazados están a la venta en Amazon. Incluyen un código de Afiliado Amazon Associates que nos cede un pequeño porcentaje de las ventas. Los productos están seleccionados por los autores del blog, pero ni Amazon ni los editores de los libros o fabricantes de los productos participan en dicha selección.

Más libros y productos en:

Microsiervos Selección