Algorithme de Christofides
De Wikipedia, l'encyclopédie encyclopedia
L'algorithme de Christofides est un algorithme d'approximation pour le problème du voyageur de commerce, dans le cas métrique, et que l'inégalité triangulaire est respectée. L'analyse de cet algorithme est due à Nicos Christofides and Anatoliy I. Serdyukov, qui l'ont découvert indépendamment en 1976[1],[2],[3].