Seminar: Semidefinite Programmierung

Dozent: Amin Coja-Oghlan

Termine

SE	Freitag	11:00 - 13:00	(RUD 26, 0.319)

Zuordnung

Hauptstudium, Seminar

Voraussetzungen

Grundstudium der Informatik oder Mathematik

Inhalte und Lernziele

Einigen Approximationsalgorithmen für NP-schwere kombinatorische Optimierungsprobleme liegt die Idee zugrunde, zunächst von dem diskreten Problem zu einem kontinuierlichen Problem, einer sog. Relaxierung, überzugehen.
Aus der Lösung des kontinuierlichen Problems, welche in Polynomzeit berechenbar ist, wird dann durch Rundungstechniken eine Lösung des kombinatorischen Optimierungsproblems gewonnen.
In diesem Seminar soll eine neuere Art von Relaxierungen, nämlich Semidefinite Programme, im Mittelpunkt stehen.

Vortragsthemen

Grundlagen: positiv semidefinite Matrizen, Dualität
effiziente Lösungsmethoden für semidefinite Programme
der MAX CUT-Algorithmus von Goemans und Williamson
verschiedene Charakterisierungen des MAX CUT-SDPs
worst-case-Instanzen für MAX CUT
die Lovasz Theta-Funktion als Relaxierung des Stabile-Menge-Problems
worst-case-Instanzen für die Theta-Funktion
Anwendung der Lovasz-Theta-Funktion auf das Stabile-Menge-Problem
die Vektorchromatische Zahl und Graphenfärbung via SDP

Empfohlene Literatur

Grötschel, Lovasz, Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer Verlag, 1998.
Helmberg, Semidefinite Programmung for Combinatorial Optimization, ZIB-Report 00-34, 2000.

zuletzt geändert am 23.01.2006 (alkox-www)