Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26004
Titel: Randomized rounding and rumor spreading with stochastic dependencies
Sonstige Titel: Randomisiertes Runden und Gerüchteverbreitung bei stochastischer Abhängigkeit
Verfasser: Huber, Anna
Sprache: Englisch
Erscheinungsjahr: 2010
SWD-Schlagwörter: Randomisierung
Rundung
Randomisierter Algorithmus
Gerücht
Stochastische Abhängigkeit
Freie Schlagwörter: Gerüchteverbreitung
randomized roundig
randomized algorithm
rumor spreading
stochastic dependency
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: Randomness is an important ingredient of modern computer science. The present thesis is concerned with two uses of randomness, viz. randomized roundings and randomized rumor spreading algorithms. The theorem of Beck and Fiala (1981) asserts that for every hypergraph and every set of vertex weights there is a rounding of the vertex weights such that the additive rounding error for all hyperedges is bounded by the maximum degree. In Chapter 2 this theorem will be extended to randomized roundings, that is, to roundings that are efficiently generated at random in such a way that each value is rounded up with probability equal to its fractional part. The larger part of this thesis deals with randomized rumor spreading algorithms. These are protocols for disseminating information on graphs. The classical randomized rumor spreading was introduced and first investigated by Frieze and Grimmett on the complete graph (1985). In Chapter 3 a generalization of their results both in terms of the model used and in terms of the underlying graph will be shown. In Chapter 4 a quasirandom rumor spreading protocol introduced by Doerr, Friedrich, and Sauerwald (2008) will be considered. We present a detailed analysis of its evolution and show that its performance and robustness match performance and robustness of the randomized rumor spreading protocol. The unifying idea is to use dependencies so as to obtain results that are superior or equal to those obtained via independent randomness.
Die Verwendung von Zufallselementen ist ein wichtiger Bestandteil der modernen Informatik. Die vorliegende Arbeit untersucht zwei Bereiche, in denen randomisierte Methoden Verwendung finden, nämlich randomisierte Rundungen und randomisierte Algorithmen zur Gerüchteverbreitung. Der Satz von Beck und Fiala (1981) sagt aus, dass es für jeden Hypergraphen und für jeden Satz von Knotengewichten eine Rundung gibt derart, dass der Rundungsfehler pro Kante vom Maximalgrad beschränkt wird. Im ersten Teil der Arbeit wird dieser Satz auf den Fall randomisierter Rundungen verallgemeinert, das heißt auf zufällige Rundungen, bei denen jede Zahl mit der Wahrscheinlichkeit entsprechend ihren Nachkommastellen aufgerundet wird. Der zweite, größere Teil der Arbeit handelt von randomisierten Algorithmen zur Gerüchteverbreitung. Das klassische "Randomized Rumor Spreading" wurde von Frieze und Grimmett (1985) eingeführt. Ihre Ergebnisse werden in Kapitel 3 sowohl hinsichtlich des Modells als auch hinsichtlich des zugrundegelegten Graphen verallgemeinert. In Kapitel 4 wird ein quasizufälliges Modell zur Gerüchteverbreitung betrachtet und gezeigt, dass es bezüglich Laufzeit und Robustheit dem klassischen Modell gleichwertig ist. Gemeinsam liegt beiden Teilen der Arbeit die Idee zugrunde, stochastische Abhängigkeiten zu nutzen um Ergebnisse zu erzielen, die den unter Verwendung stochastischer Unabhängigkeit erzielten gleichwertig oder überlegen sind.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-34254
hdl:20.500.11880/26060
http://dx.doi.org/10.22028/D291-26004
Erstgutachter: Doerr, Benjamin
Tag der mündlichen Prüfung: 1-Okt-2010
SciDok-Publikation: 15-Nov-2010
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Dissertation_1345_Hube_Anna_2010.pdf513,98 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.