Seminar Approximationsalgorithmen, Sommer 2003

Seminar Approximationsalgorithmen (LV DX9), Sommer 2003

Zeit und Ort:

Donnerstag 11:30 - 13:00, Raum 2/41/238

Inhalt:	Für viele kombinatorische Optimierungsprobleme gibt es vermutlich keine schnellen Lösungsverfahren (NP-schwere Probleme), wohl aber effiziente Approximationsalgorithmen, die Lösungen mit Gütegarantie erzeugen. Dieses Seminar soll an Hand des Buches Approximation Algorithms von V. V. Vazirani in Form einer Vorlesung von Studenten für Studenten in grundlegende Techniken und Resultate dieses Gebiets einführen.
Zielgruppe:	wob.: MMM6,8, IMM6,8, WMM6,8
Vorwissen:	Lineare Optimierung, Grundbegriffe aus Graphen- und Komplexitätstheorie
Abschluss:	Seminarschein bei aktiver Teilnahme und Vortrag

Übung 1 (ps-file), verteilt am 15.10., Abgabe am 22.10.
Übung 2 (ps-file), verteilt am 22.10., Abgabe am 29.10.
Übung 3 (ps-file), verteilt am 29.10., Abgabe am 5.11.
Übung 4 (ps-file), verteilt am 5.11., Abgabe am 12.11; in Aufgabe 2 Summenzeichen ergänzt am 13.11.
Übung 5 (ps-file), verteilt am 12.11., Abgabe am 19.11; in Aufgabe 5 Korrektur m1=(a+d)(alpha+delta) am 13.11.
Übung 6 (ps-file), verteilt am 19.11., Abgabe am 26.11.
Übung 7 (ps-file), verteilt am 26.11., Abgabe am 3.12.
Übung 8 (ps-file), verteilt am 3.12., Abgabe am 10.12.
Übung 9 (ps-file), verteilt am 10.12., Abgabe am 17.12.
Übung 10 (ps-file), verteilt am 17.12., Abgabe am 7.1.2003.
Übung 11 (ps-file), verteilt am 7.1., Abgabe am 14.1.
Übung 12 (ps-file), verteilt am 14.1., Abgabe am 21.1.
Übung 13 (ps-file), verteilt am 21.1., Abgabe am 28.1.
Übung 14 (ps-file), verteilt am 28.1., Abgabe am 4.2.

Last modified: Mon Mar 31 17:33:16 CEST 2003