• AG Optimierung
• Impressum

Seminar "Approximationsalgorithmen in der kombinatorischen Optimierung"

Obwohl kombinatorische Optimierungsprobleme häufig relativ einfach beschrieben werden können, gibt es für viele Problemklassen vermutlich keine schnellen (polynomialen) Algorithmen zur Bestimmung einer beweisbar optimalen Lösung. Um dennoch in akzeptabler Zeit gute Lösungen zu erhalten, werden Approximationsalgorithmen entwickelt, die für zahlreiche kombinatorische Optimierungsprobleme Lösungen von beweisbarer Güte in vertretbarer Zeit berechnen. In diesem Seminar werden verschiedene Ansätze zur Entwicklung von Approximationsalgorithmen besprochen und anhand klassischer kombinatorischer Optimierungsprobleme diskutiert.

Inhalt des Seminars

Grundlage für das Seminar ist das Buch "Approximation Algorithms" von Vijay Vazirani, Springer 2001, sowie aktuelle Zeitschriftenartikel. Kenntnisse in linearer und diskreter Optimierung werden vorausgesetzt.

Voraussetzungen

Kenntnisse aus den Bachelor Vorlesungen zur Optimierung (Operations Research I und II) werden vorausgesetzt.

Vorbesprechung

Eine Vorbesprechung mit Themenvergabe findet am 14.10.2013 um 14:00 Uhr statt; Treffpunkt um 14:00 Uhr in D13.04. Das Seminar wird voraussichtlich als Blockseminar stattfinden; die Terminplanung findet in der Vorbesprechung statt.