Satz 31 (TreeTSP und MinMTSP)
TSP ist ein 2-Approximationsalgorithmus für MinMTSP
Beweis: Kanten im Graph verdoppeln, Euler Kreis ablesen und Rundreise berechnen, da doppelte Kanten -> maximal doppeltes Gewicht
Satz 32 (Christofides und MinMTSP)
1,5 Approximationsalgorithmus für MinMTSP
Satz 33 (MinPart - r-PartAS)
r-PartAS ist r-Approximationsalgorithmus für MinPart
Satz 34 (GSAT, MaxSAT)
GSAT ist 2-Approximationsalgorithmus für MaxSAT
MaxSAT
I = AL Formeln in KNF mit Variablenmenge
S = Belegung von Variablen mit {0,1}
M = Anzahl der durch Belegung erfüllten Klauseln
T = Maximiere
Last changeda year ago