Komplexität von Algorithmen, Satz 32
Channel: ThI Videos
Date: 31/03/2021

In diesem Video betrachten wir eine Optimierung vom Algorithmus TreeTSP für MinMTSP. Diese Optimerung wurde von Christofides gefunden und basiert auf der Berechnung von Matchings mit minimalem Gewicht. Hierzu werden wir zunächst Matchings definieren.


0:00 Definition: Matching
1:04 Satz 32
1:20 Christofides am Beispiel
2:55 Christofides formal
5:49 Christofides-Heuristik ist 3/2-Approximationsalgorithmus für MinMTSP