Arbeitsrichtung
Anwendung und Untersuchung probabilistischer Methoden im Hinblick auf algorithmische und strukturelle Fragen in der Diskreten Mathematik
Zusammenfassung
Der Entwurf und die Analyse von Algorithmen ist eng verknüpft mit Einsichten in die Struktur der Objekte, die die Algorithmen als Eingabe erhalten. Das zentrale Thema des Forschungsvorhabens ist es, diese Verknüpfung im Hinblick auf den Einfluss des Zufalls zu untersuchen - wie wirkt sich die Hinzunahme von Zufall auf algorithmische und strukturelle Fragestellungen in der Diskreten Mathematik aus?
Der Zufall ist hierbei gleichermaßen Forschungsobjekt wie Untersuchungsmethode. Im Hinblick auf Strukturerkenntnisse wird einerseits nach Eigenschaften gesucht, die zufällige Objekte mit hoher Wahrscheinlichkeit besitzen, andererseits charakterisieren wir Objekte durch Benutzung des Zufalls. Und auch unter algorithmischen Aspekten setzt sich diese Dualität fort: Einerseits wird untersucht, wie sich Algorithmen auf zufälligen Eingaben verhalten, andererseits werden Verfahren analysiert, deren Entscheidungen zufällige Komponenten aufweisen.
Auf der algorithmischen Seite gilt das Interesse kombinatorischen Optimierungsproblemen. Dadurch treten ganz natürlich Polytope, Graphen und partielle Ordnungen als Forschungsobjekte von Strukturuntersuchungen in den Mittelpunkt. Die Forschergruppe bündelt dabei die individuellen Erfahrungen und Kompetenzen, die die beteiligten Arbeitsgruppen in den letzten Jahren mit unterschiedlichen Ansätzen in dem Spannungsfeld von Algorithmen, Struktur und Zufall gewonnen haben.
Die Forschungsprojekte
Das Programm der Forschergruppe ist auf die einzelnen Arbeitsgruppen aufgeteilt und wird vertikal in die folgenden sechs Projekte gegliedert dargestellt:
- Stabile Mengen und spezielle Graphenklassen
- Kombinatorische Online-Planung
- Evolution und Phasenübergänge
- Zufall bei Entwurf und Analyse von diskreten Algorithmen
- Geometrie und Kombinatorik von 0/1-Polytopen
- Enumeration und zufälliges Erzeugen
Leitfragen des Forschungsprogramms
Um die inhaltliche Verflechtung der Projekte und ihre Unterordnung unter das gemeinsame Thema deutlich zu machen, stellen wir der vertikalen Gliederung der Forschergruppe in Projekte eine horizontale Gliederung voran, die das Forschungsprogramm unter vier Leitfragen subsumiert:
English