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 MitarbeitProf. Dr. B. Korte,
Prof. Dr. D. Rautenbach,
Prof. Dr. J. Vygen