Design und Analyse stochastischer Algorithmen auf kombinatorischen Strukturen

In der vorliegenden Arbeit werden randomisierte Algorithmen, basierend auf ergodischen Markov-Ketten, konstruiert und analysiert. Die Grundräume dieser Markov-Ketten sind endliche Mengen kombinatorischer Strukturen, wie zum Beispiel die aufspannenden Bäume eines Graphen, die eulerschen Orientierungen eines Euler-Graphen oder die 3-Färbungen eines Graphen. Ein solcher Algorithmus liefert ein zufälliges Element des Grundraumes, dessen Verteilung annähernd der stationären Verteilung der Markov Kette entspricht. Dadurch kann eine Abschätzung für die Mächtigkeit des Grundraumes ermittelt werden. Besonderen Wert wird auf die Analyse der Laufzeit dieser Algorithmen gelegt, die von der Mischzeit der jeweiligen Markov Kette dominiert wird. Hierzu werden die Methode der kanonischen Pfade, Multi-Commodity Flows, Pfad-Coupling und Vergleichsmethoden eingesetzt.

Author dc:creator

• Fehrenbach, Johannes

Contributors dc:contributor

• Rüschendorf, Ludger

• Mischzeitabschätzung
• kanonische Pfade
• Pfad-Coupling
• aufspannende Bäume
• eulersche Orientierungen
• Markov Chain
• Mixing Time
• sampling approximately at random
• Spanning Trees
• Eulerian Orientations

Repository record source_url

https://freidok.uni-freiburg.de/data/783

OAI identifier oai:identifier

oai:freidok.uni-freiburg.de:783