Hauptgrundlage des Seminars ist das Buch Randomized Algorithms von Rajeev Motwani und Prabhakar Raghavan (Cambridge University Press 1995, ISBN 0-521-47465-5). Die angegebenen Quellen sind zumeist Kapitel oder Abschnitte dieses Buches. Weiter werden ein paar neue Originalarbeiten, u. a. von David Karger (STOC'96, STOC'97), hinzugezogen.
Das Seminar findet montags von 14-16 Uhr im Seminarraum Lennéstraße 2 statt.
Datum | Name | Thema | Hauptquelle | |
20.10. | Christopher Anhalt | Grundlagen aus Wahrscheinlichkeits- und Spieltheorie | 1-3 | |
27.10. | Onno Garms | Chernoff-Schranken, Zufälliges Runden | 4.1-4.3 | |
3.11. | Toàn Phan Huy | Die Probabilistische Methode | 5 | |
10.11. | Markus Lilienthal | Zufallswege | 6.1-6.6 | |
17.11. | Peter Küsters | Randomisierte Datenstrukturen | 8 | |
24.11. | Martin Kutz | Geometrische Algorithmen I | 9.1-9.5 | |
1.12. | Martin Kutz | Geometrische Algorithmen II | 9.6-9.9 | |
8.12. | Sven Peyer | Lineare Optimierung | 9.10 | |
15.12. | Jürgen Werber | Kürzeste Wege | 10.1 | |
12.1. | Jürgen Werber | Minimal spannende Bäume | 10.3 | |
19.1. | Ulrich Brenner | Minimale Schnitte | 10.2 | |
26.1. | Ulrich Brenner | Maximale Flüsse | [Karger 1997] | |
2.2. | Christopher Mues | Online-Algorithmen | 13 |
Prof. Dr. B. Korte, Dr. J. Vygen