Skip navigation
Please use this identifier to cite or link to this item: http://dx.doi.org/10.25673/2241
Title: Markov Chain Monte Carlo algorithms for the uniform sampling of combinatorial objects
Author(s): Rechner, Steffen
Advisor(s): Müller-Hannemann, Matthias
Brandes, Ulrik
Granting Institution: Martin-Luther-Universität Halle-Wittenberg
Issue Date: 2018
Extent: 1 Online-Ressource (188 Seiten)
Type: Hochschulschrift
Exam Date: 04.06.2018
Language: English
Publisher: Universitäts- und Landesbibliothek Sachsen-Anhalt
URN: urn:nbn:de:gbv:3:4-22564
Abstract: In dieser Arbeit untersuche ich die Effizienz von Markov-Chain Monte Carlo (MCMC) Algorithmen zum gleichverteilten Erzeugen zufälliger kombinatorischer Strukturen. Zu diesem Zweck habe ich eine Software namens marathon entwickelt, welche ich zur Berechnung struktureller Eigenschaften von Markov-Ketten einsetze, die rein analytisch schwer zu bestimmen wären. Ich verwende diese Software, um MCMC-Algorithmen aus drei Problemklassen zu untersuchen. Zunächst untersuche ich drei bekannte Methoden zum Erzeugen zufälliger bipartiter Graphen mit festen Knotengraden. Unter anderem zeige ich, welcher Algorithmus am besten für den Einsatz in speziellen ökologischen Anwendungen geeignet ist. Anschließend betrachte ich das Erzeugen zufälliger bipartiter Graphen mit beschränkten Knotengraden. Ich führe zwei neue MCMC-Algorithmen ein und untersuche auf experimentellem Wege deren Effizienz. Schließlich analysiere ich Algorithmen zum zufälligen Erzeugen perfekter Matchings in bipartiten Graphen. Dabei identifiziere ich Initialzustände, die eine polynomielle beziehungsweise exponentielle Mischzeit besitzen.
In this thesis, we discuss a family of sampling methods known as Markov chain Monte Carlo (MCMC) algorithms. To support the analysis of such algorithms,we developed the software tool marathon, designed to determine properties of Markov chains that are usually hard to find analytically. We apply our software to experimentally assess the efficiency of several MCMC algorithms from three sampling applications. First, we address three well-known MCMC algorithms for the uniform sampling of bipartite graphs with fixed degrees. In a set of experiments, we show which sampling algorithm works best in certain types of ecological applications. Motivated by the work with incomplete data, we next address the uniform sampling of bipartite graphs whose degrees lie in prescribed intervals. After introducing two new MCMC algorithms, we give a proof of their correctness and experimentally assess their efficiency. Finally, we address the uniform sampling of perfect matchings in bipartite graphs. In a set of experiments with two special classes of bipartite graphs, we identify initial states that require a polynomial and an exponential number of steps.
URI: https://opendata.uni-halle.de//handle/1981185920/9013
http://dx.doi.org/10.25673/2241
Open access: Open access publication
Appears in Collections:Informatik, Informationswissenschaft, allgemeine Werke

Files in This Item:
File Description SizeFormat 
Dissertation-5.pdf15.35 MBAdobe PDFThumbnail
View/Open
Show full item record BibTeX EndNote


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.