Forschungsinstitut für Diskrete Mathematik

Seminar Diskrete Optimierung

Sommersemester 2006

Thema: Approximation von Metriken

Termin: montags 14-16 Uhr

In diesem Seminar geht es um Einbettungen endlicher Metriken in einfache metrische Räume. Dabei möchte man einerseits die Dimension des Raumes minimieren, in den man einbettet. Andererseits möchte man die Verzerrung der metrischen Eigenschaften minimieren, die die Einbettung mit sich bringt. Diese beiden Ziele sind offenbar gegenläufig.
Es werden eine Reihe positiver wie negativer Resultate zu Fragen solcher Einbettbarkeit thematisiert. Darüber hinaus geht es um interessante algorithmische Anwendungen dieser Einbettungen, mit deren Hilfe man für einige rein kombinatorische Probleme (z.B. bandwidth, sparsest cut, multicommodity flows) erstaunliche Approximationsalgorithmen beschreiben konnte.

Nr.	Datum	Name	Thema	Betreuung
1	10.4.	Malte Beecken	Der Satz von Johnson und Lindenstrauss	Jürgen Werber
2	24.4.	Hanna Sdunzik	Algorithmische Variante des Satzes von Bourgain	Markus Struzyna
3	8.5.	Markus Moll	Untere Schranken für die Verzerrung	Christoph Bartoschek
4	15.5.	Astrid Gösling	Einbettung von Baummetriken	Jens Maßberg
5	22.5.	Katja Gundelach	Approximation von Metriken durch Baummetriken	Ulrich Brenner
6	29.5.	Richard Schmied	Sparsest Cut	Ulrich Brenner
7	12.6.	Thomas Windheuser	Optimale lineare Anordnung	Stephan Held

Scheinkriterien:

erfolgreicher Seminarvortrag, regelmäßige Teilnahme an den Veranstaltungen und aktive Mitarbeit

Prof. Dr. B. Korte,
Prof. Dr. D. Rautenbach,
Prof. Dr. J. Vygen