Direkt zum Inhalt

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.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos