Beweise, dass der folgende Algorithmus ein 2-approximations Algorithmus für das MAX3CNF Problem ist (MAX3CNF: gegeben Formel F in 3CNF, gesucht Wahrheitswertbelegung, sodass maximale Anzahl von Klauseln erfüllt sind):
REPEAT
Wähle das Literal, dass in der größten Anzahl vn Klauseln vorkommt
Setze die entsprechende Variable auf wahr falls das Literal positiv ist, sonst auf falsch
Entferne aus F alle Klauseln, die erfüllt sind
UNTIL Formel ist erfüllt oder alle Variablen haben Werte zugewiesen bekommen.
In der Vorlesung haben wir gehört, dass, falls P =/= NP, TSP sich für konstantes e>1 nicht e-approxmieren lässt.
Beim Euclidischen TSP gehorchen die Kosten zwischen den Städten folgender Dreiecksungleichung: d(u,w) <= d(u,v)+d(v,w).
Zeige, dass das Euclidische TSP Problem 2-approximierbar ist.
Hinweis: Mittels minimum spanning tree.