Approximationsalgorithmen: Was wurde wann gemacht?

Nr.	Datum	Stoff
1	14.10.03	Skriptmitschreibeaktion angeleiert. Liste mit empfohlener Literatur angeschrieben. Optimierungsproblem definiert. Notationen festgelegt. Notation am Beispiel TSP erläutert. "Entscheidungsvariante" definiert, Approx.algorithmus definiert. "Absolute Güte" sowie "absolute worst-case-Güte" definiert. Begonnen mit dem Satz von Vizing zur Kantenfärbbarkeit, der einen Algorithmus beschreibt, der einen Graphen mit Delta(G)+1 Farben kantenfärbt. Das Umfärbungslemma angeschrieben.
2	15.10.03	Das Umfärbungslemma bewiesen. Beispiel für Umfärbung vorgenommen. Beispiel, dass durch "Aufblähen" von Zahlen in der Eingabe bewiesen werden kann, dass (wenn P<>NP) bestimmte Probleme keinen Polynomialzeitapproximationsalgorithmus mit absoluter worst-case-Güte haben können. (Bsp: Ruchsackproblem). Definition von relativer Güte, relativer worst-case-Güte und asymptotischer worst-case-Güte. Beispiel, wo die worst-case-Güten unterschiedlich sind. Beispiel für Algorithmus, der relative worst-case-Güte 2 hat: Greedy-Algorithmus für das Vertex Cover-Problem. Begonnen mit dem Beweis, dass es in der Tat ein Algorithmus mit Güte 2 ist.
3	21.10.03	Analyse für Vertex Cover beendet, Algorithmus für gewichtetes Vertex Cover vorgestellt und analysiert, Zusammenhang zwischen MINSAT und Vertex Cover hergestellt. Greedy-Algorithmus für das Independent Set-Problem vorgestellt und nachgewiesen, dass er eine unabhängige Menge der Größe n/(d_+1) berechnet, wenn d_ der Durchschnittsgrad ist.
4	22.10.03	Eine etwas schärfere Analyse des Greedy-Algorithmus vorgestellt, die zeigt, dass die Güte mindestens (d_+2)/2 ist. Beispiel skizziert, wo der Greedy-Algorithmus tatsächlich um fast diesen Faktor "daneben liegt". Problem Set Cover definiert und Greedy-Algorithmus dafür vorgestellt. Mit Analyse dieses begonnen.
5	28.10.03	Analyse des Greedy-Algorithmus für Set Cover beendet, Beispiel vorgestellt, wo der Algorithmus fast um den Faktor H(n) "daneben liegt". Problem Hitting Set als äquivalentes Problem zu Set Cover erwähnt. Anwendung von Set Cover auf das Superstringproblem. Greedy-Algorithmus vorgestellt, anschließend Reduktion des Superstringproblems auf Set Cover. Beweis, dass der Superstring, den man mit Hilfe der Set-Cover-Lösung bekommt, höchstens doppelt so lang ist wie der optimale Superstring. (Problem aber: Man muss die optimale Lösung von Set Cover approximieren!)
6	29.10.03	Steinerbäume: Definition. Gezeigt, dass man sich auf metrische Eingaben konzentrieren kann. Einen Approximationsalgorithmus mit Güte 2 für das metrische Problem vorgestellt. Beispiel, wo der Algorithmus "um Faktor 2 daneben liegt." Nachgewiesen, dass TSP schlecht zu approximieren ist (wenn P<>NP). Algorithmus von Christofides. Beispiel, wo dieser um den Faktor fast 3/2 "daneben liegt".
7	04.11.03	Cuts und Verallgemeinerungen davon: Maxcut, verschiedene Approx.algorithmen für das Problem mit Güte 2 bzw. Algorithmen, die bei bestimmten Graphklassen besser sind. (Wenn zum Beispiel der maximale Grad beschränkt ist.) Rekursive Verwendung des Algorithmus für k-MAXCUT für k>2. Definition Multiway Cut.
-	05.11.03	fällt aus, da ab 14 Uhr veranstaltungsfrei wegen einer Informationsveranstaltung gegeben wurde.
8	11.11.03	Multiway Cut, isolierende Schnitte, wie berechnet man isolierende Schnitte, Güte des Algorithmus für Multiway Cut, der isolierende Schnitte ausgibt. Bsp., dass Analyse nicht verbesserbar. Minimum k-Cut, Def. von Gomory-Hu-Bäumen, Beweis, dass die erste Bedingung nur für benachbarte Kanten im Baum gelten muss.
9	12.11.03	Bsp. für Gomory-Hu-Baum. Algorithmus für Minimum k-Cut analysiert, der die Schnitte aus dem Gomory-Hu-Baum verwendet.Bsp., dass Analyse nicht verbesserbar. Def., was eine schwach submodulare Funktion ist. Beweis, dass Kapazitätsfunktion auf Schnitten schwach submodular ist. Def. von kreuzenden Teilmengen und kreuzenden Schnitten.
10	18.11.03	Bsp. für kreuzende Schnitte. Beweis, dass man aus kreuzenden minimalen Schnitten weitere Schnitte als minimal herleiten kann. Beweis, dass zu minimalem s-t-Schnitt und x ungleich y ein minimaler, den s-t-Schnitt nicht-kreuzender x-y-Schnitt existiert. Algorithmus zur Berechnung eines Gomory-Hu-Baums erklärt.
11	19.11.03	Beispiel für Ablauf des Gomory-Hu-Baum-Algorithmus. Invarianten genannt, die beim Ablauf erhalten bleiben und bewiesen, dass diese erhalten bleiben. Begonnen mit dem k-Center-Problem: Def. dominierende Knotenmenge. Def. Dominating-Set-Problem. Maximale unabhängige Menge ist auch dominierende Knotenmenge. k-Center-Problem definiert. Zusammenhang zwischen dominating-set-Problem und k-Center-Problem. Beweis der Problemäquivalenz begonnen.
12	25.11.03	Beweis der Problemäquivalenz beendet. G2 definiert und das Quadratlemma bewiesen, das eine Aussage über Zusammenhang zwischen unabhängiger Menge in G2 und dominierender Menge in G macht. Algorithmus metrisches k-Center vorgestellt und relative Güte höchstens zwei nachgewiesen. Beispiel, dass die Analyse exakt ist. Beweis, dass es (falls P ungleich NP) keine besseren Approx.algorithmen geben kann. Das metrische W-Center-Problem: Definition. Gewichtete Variante des Quadratlemmas. Algorithmus für das W-Center-Problem vorgestellt. Begonnen mit dem Beweis der relativen Güte 3.
13	26.11.03	Beweis der Güte 3 beendet. Beispiel dafür, dass die Analyse exakt ist. Begonnen mit dem Feedback-Vertex-Set-Problem (FVS-Problem). Definition von FVS, von "inklusionsminimalem FVS". Def. zyklomatische Zahl, Zyklenraum. Beweis, dass cyc(G)=|E|-|V|+kappa(G). "Additivitätseigenschaft". Definition von deltaG(v). Beweis zu einer Formel für deltaG(v). Gezeigt, dass cyc(G) kleiner gleich delta(F). (Dabei ist delta(F) die Summe aller delta-Werte von Knoten aus F und F ein FVS.)
14	02.12.03	Gezeigt, wie sich die Delta-Werte auf einem Teilgraphen H von G durch die Delta-Werte von G abschätzen lassen. Gezeigt, dass für inklusionsminimale FVS F die Zahl 2*cyc(G) eine obere Schranke ist für die Summe der Deltawerte der Knoten aus F. (Dies hat sich etwas länger hingezogen, da im Vazirani-Buch ein Fehler enthalten ist.) Definition zyklomatische Zahl.
15	03.12.03	Definition zyklomatische Zahl. Gezeigt, dass man bei zyklomatischer Gewichtsfunktion via Greedyalgorithmus eine Güte von 2 bekommt. Die Technik des Layering erklärt: Algorithmus zerlegt eine beliebige Gewichtsfunktion in eine Summe von zyklomatischen Gewichtsfunktion plus einer (beliebigen) Gewichtsfunktion auf einem Graphen, der kresifrei ist. Algorithmus: 2 Phasen, Dekompositionsphase, Erweiterungsphase. Güte 2 für den Algorithmus nachgewiesen und Beispiel gegeben, dass die Analyse exakt ist. Begonnen mit dem Problem "kürzester Superstring", gezeigt, dass es bei diesem Problem hauptsächlich darauf ankommt, die Reihenfolge der Strings im kürzesten Superstring zu kennen.
16	09.12.03	Kürzeste Superstrings: Präfixgraph, Äquivalenz zu TSP-Tour, Def. Kreisüberdeckung (KÜ), wie berechnet man billigste KÜ, Umkehrung: Wie Superstring aus KÜ, Def. von alpha(C) und sigma(C), Algorithmus mit Güte 4 vorgestellt und begonnen mit dem Beweis seiner Güte.
17	10.12.03	Beweis zur Güte 4 beendet. Algorithmus mit Güte 3 vorgestellt: "Kompression" definiert, Beweis der Güte 3 bei Benutzung eines gut komprimierenden Algorithmus. Kompressionsalgorithmus vorgestellt, der mindestens die Hälfte der optimalen Kompression erreicht.
18	16.12.03	PTAS definiert, PAS, FPAS für Rucksackproblem durch Runden, ein Approximationsalgorithmus für das Bin Packing Problem, ein negatives Resultat für das Bin Packing Problem, ein asymptotisches PAS für das Bin Packing Problem.
19	17.12.03	Fortsetzung asymptotisches PAS für das Bin Packing Problem. LP-basierte Approximationsalgorithmen. Das Konzept der LP-Dualität.
20	06.01.04	Dualitätstheorem, das schwache Dualitätstheorem inkl. Beweis. Flussalgorithmen und LP-Dualität (MINCUT=MAXFLOW). Begonnen mit "dualem Fitting" für Set Cover.
21	07.01.04	Intuitive Sichtweise des dualen Set Cover-Problems als Packingproblem. Greedy-Set-Cover-Algorithmus, erneut analysiert mit dualem Fitting. Beispiel, dass der Integrality Gap tatsächlich Omega(ln n) ist. Verallgemeinerung von Set Cover: Set Multicover und eingeschränktes Set Multicover. Primales und duales LP für das eingeschränkte Set Multicover. Greedy-Algorithmus für das Problem. Begonnen mit der Analyse dieses Algorithmus: Vektoren alpha und beta definiert und auf diesen den dualen Zielfunktionswert ausgerechnet.
22	13.01.04	Nachgewiesen, dass alpha und beta dual zulässig sind. Set Cover: Ein Algorithmus, der deterministisches Runden benutzt. Ein Beispiel, dass die erreichte Güte f tatsächlich auch genau f sein kann. Ein Algorithmus für Set Cover, der randomisiertes Runden verwendet.
23	14.01.04	Halbzahligkeit von Vertex Cover bewiesen. Relaxierte komplementäre Schlupfbedingungen definiert. Am Beispiel von Set Cover gezeigt, wie man mit diesen das so genannte primal-duale Schema aufstellen kann. Begonnen mit randomisiertem Runden für MAXSAT. Das "Klausellemma" formuliert und mit dem Beweis begonnen.
24	20.01.04	Das Klausellemma bewiesen. Gezeigt, dass durch randomisiertes Runden eine relative Güte von mindestens (1-1/e) vorliegt. Algorithmus MIX betrachtet und seine relative Güte als 3/4 nachgewiesen. Potenzialbasiertes deterministisches Runden als Alternative zu randomisiertem Runden. Wie erhält man aus Approx.algorithmus für MAXSATCC einen für SET COVER?
25	21.01.04	Beweis für "SET COVER via MAXSATCC" beendet. Wie approximiert man monotone MAXSATCC-Instanzen? Paarweise potenzialbasiertes Runden betrachtet und für monotone MAXSATCC-Instanzen angewendet. MAXCUT als MAXSAT-Problem formuliert und dies als eigentlich ungeeignet entlarvt. Anschließend direkt ein LP für MAXCUT und MAXCUTCC aufgestellt.
26	27.01.04	Gezeigt, dass man aus dem LP für MAXCUT bzw. MAXCUTCC einen Algorithmus mit Güte (1/2) bekommt. Motiviert, warum es Sinn macht, sich MAX2SATCC anzuschauen. Begonnen mit MAX2SATCC, Def. pure und gemischte Klauseln, 3-phasigen Algorithmus erläutert. Begonnen mit der Analyse: Aussage, wie nach der 1. Greedy-Preprocessing-Phase die Koeffizienten der übrig gebliebenen Zielfunktion aussehen.
27	28.01.04	Bewiesen, dass man die Koeffizienten nach der ersten Phase abschätzen kann. Gezeigt, dass in der dritten (Korrektur-)Phase der Wert der Zielfunktion sich nur geringfügig ändert.
28	03.02.04	Gezeigt, dass OPT_CC mindestens Omega(a*a) ist. Begonnen mit dem Kapitel "Semidefinite Programmierung": Grundlagen der Matrizentheorie. Semidefinite Programme definiert, Beispiele dafür, gezeigt, dass LP Spezialfall von Semidefiniter Programmierung ist. "Mathematisches Programm" für MAXCUT aufgestellt und dieses relaxiert.
29	04.02.04	Aus dem mathematischen Programm ein semidefinites Programm hergeleitet. Rundungsprozedur mit Hilfe von Hyperebenen erklärt. Analysiert, dass im Erwartungswert mindestens 0.878 * OPT viele Kanten im Schnitt liegen. Schließlich auch vorgeführt, wie man MAX2SAT ebenfalls mit Hilfe der semidefiniten Programmierung mit Güte 0.878 lösen kann.

Stand: 29 von 29 Vorlesungen sind vorüber