Christofides algorithm
Algoritmo de Christofides
- Date
- 1976 · confidence high
- Place
- London, England, United Kingdom
- Credited to
- Nicos Christofides (1976) and, independently, Anatoliy Serdyukov (1976, published 1978)
- Field
- Knowledge & symbols
What it is
Nicos Christofides devised an algorithm giving approximate solutions to the travelling salesman problem in metric spaces, guaranteeing a result at most 50% worse than optimal.
What it led to
- Approximation algorithms in combinatorial optimization
- Logistics route planning
- Electronic circuit design
- A standard reference in complexity theory