Forschungsinstitut für Diskrete Mathematik

Seminar Diskrete Optimierung

Sommersemester 1997


Thema:
Neue Approximationsalgorithmen
mittels semidefiniter Programme

Mit ihrer Arbeit Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming (J. ACM 42 (1995), 1115-1145) haben Michel Goemans und David Williamson eine neue Klasse von Approximationsalgorithmen begründet.
Diese basieren darauf, statt einer LP-Relaxierung des Ausgangsproblems eine (bessere) nichtlineare Relaxierung, eben als ``semidefinites Programm'', zu betrachten.
Semidefinite Programme sind eine Verallgemeinerung von Linearen Programmen (LPs), die - ähnlich wie diese - Dualitätssätze und polynomielle Algorithmen erlauben; siehe z. B. die Arbeit von Farid Alizadeh: Interior point methods in semidefinite programming with applications to combinatorial optimization (SIAM J. Optim. 5 (1995), 13-51).
Neben den beiden obengenannten Arbeiten werden auch darauf aufbauende Anwendungen auf einige andere kombinatorische Optimierungsprobleme behandelt.

Alle zwölf Vorträge sind bereits vergeben. Das Seminar findet immer montags von 14-16 Uhr im Seminarraum, Nassestraße 2, statt, beginnend am 7. April.

gez. J. Vygen