AG 1, AG 2, AG 3, AG 4   Info

Expert Audience

-- Not specified --

Saarbrücken

Vor etwa 20 Jahren veröffentlichte L. Lovász eine überraschende Schranke für die Shannon
Kapazität von Graphen, zu deren Berechnung eine lineare Kostenfunktion über positiv
semidefinite Matrizen optimiert werden musste. Die Schranke war, wie sich bald
herausstellte, im Prinzip in polynomialer Zeit berechenbar, jedoch betrachtete man das
Ergebnis lange Zeit als hauptsächlich von theoretischer Relevanz. Gute 10 Jahre später
änderte sich diese Sichtweise grundlegend mit der Entwicklung von Innere-Punkte Verfahren
für semidefinite Programme. Obwohl Innere-Punkte Verfahren bis heute nur für relativ kleine
Probleme sinnvoll anwendbar sind, stärkte ihre Existenz das Interesse an semidefiniten
Relaxierungen kombinatorischer Optimierungsprobleme und deren Approximationsgüte. Seit
Kurzem gibt es nun auch algorithmische Ansätze, die sich zur näherungsweisen Berechnung
großer semidefiniter Programme eignen. Die Zeit scheint reif, sich Anwendungen dieser
Techniken in der Praxis zu widmen. In meinem Vortrag werde ich, beginnend mit der Shannon
Kapzität, einige kombinatorische Anwendungen der semidefiniten Optimierung, wie das
Clustern von Daten und die Frequenzzuweisung im Mobilfunk, ansprechen und, nach einem
kurzen Abstecher in die Theorie der Semidefiniten Optimierung, einen Überblick über
algorithmische Methoden zur Lösung semidefiniter Programme geben.

Christian Schulte

--email hidden

passcode not visible

logged in users only