Lexikon der Mathematik: Christofides, Algorithmus von
ein approximativer Algorithmus für das TSP (Traveling-Salesman- Problem) unter der Nebenbedingung, daß die n Orte in einem euklidischen Raum liegen und die Wegkosten den euklidischen Abständen entsprechen.
Der Algorithmus von Christofides garantiert in kubischer Rechenzeit eine Güte (Güte eines Algorithmus) von 3/2.
Inzwischen gibt es für das so eingeschränkte TSP für jedes ϵ > 0 einen approximativen Algorithmus, der in polynomieller Zeit eine Güte von 1 + ϵ garantiert.
Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.