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