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
|