Please use this identifier to cite or link to this item: http://dx.doi.org/10.25673/2241
Full metadata record
DC FieldValueLanguage
dc.contributor.refereeMüller-Hannemann, Matthias-
dc.contributor.refereeBrandes, Ulrik-
dc.contributor.authorRechner, Steffen-
dc.date.accessioned2018-09-24T12:37:05Z-
dc.date.available2018-09-24T12:37:05Z-
dc.date.issued2018-
dc.identifier.urihttps://opendata.uni-halle.de//handle/1981185920/9013-
dc.identifier.urihttp://dx.doi.org/10.25673/2241-
dc.description.abstractIn 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.-
dc.description.abstractIn 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.eng
dc.description.statementofresponsibilityvorgelegt von Steffen Rechner-
dc.format.extent1 Online-Ressource (188 Seiten)-
dc.language.isoeng-
dc.publisherUniversitäts- und Landesbibliothek Sachsen-Anhalt-
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/-
dc.subject.ddc000-
dc.titleMarkov Chain Monte Carlo algorithms for the uniform sampling of combinatorial objects-
dcterms.dateAccepted2018-06-04-
dcterms.typeHochschulschrift-
dc.typePhDThesis-
dc.identifier.urnurn:nbn:de:gbv:3:4-22564-
local.publisher.universityOrInstitutionMartin-Luther-Universität Halle-Wittenberg-
local.subject.keywordsZufallsauswahl; Markov-Chain Monte Carlo; zufällige Graphen; Binärmatrizen mit beschränkten Randsummen; bipartite Graphen mit beschränkten Knotengraden; perfekte Matchings in bipartiten Graphen; Analyse von Zustandsgraphen-
local.subject.keywordsrandom sampling; Markov-Chain Monte Carlo; random graphs; binary matrices with restricted margins; bipartite graphs with restricted degrees; perfect matchings in bipartite graphs; state graph analysiseng
local.openaccesstrue-
dc.identifier.ppn1024921875-
local.accessrights.dnbfree-
Appears in Collections:Informatik, Informationswissenschaft, allgemeine Werke

Files in This Item:
File Description SizeFormat 
Dissertation-5.pdf15.35 MBAdobe PDFThumbnail
View/Open