Algoritmo de Christofides
Christofides algorithm
- Fecha
- 1976 · fiabilidad alta
- Lugar
- Londres, Inglaterra, Reino Unido
- Autoría
- Nicos Christofides (1976) y, de forma independiente, Anatoli Serdiukov (1976, publicado en 1978)
- Ámbito
- Saber y símbolos
Qué es
Nicos Christofides ideó un algoritmo que da soluciones aproximadas al problema del viajante en espacios métricos, garantizando un resultado a lo sumo un 50% peor que el óptimo.
A qué dio paso
- Algoritmos de aproximación en optimización combinatoria
- Planificación de rutas logísticas
- Diseño de circuitos electrónicos
- Referencia estándar en teoría de la complejidad