Schwellen in halbzufälligen Prozessen und Grapheinbettungen

Ein stochastischer Prozess besteht aus einer Abfolge von Schritten, bei denen bei jedem Schritt eine neue Zufallseingabe bereitgestellt wird. Stochastische Prozesse sind von zentraler Bedeutung für das Studium der Wahrscheinlichkeitstheorie und beschreiben viele Naturphänomene in der physikalischen Welt. Aufgrund der unbeaufsichtigten Natur der meisten stochastischen Prozesse stellt sich jedoch häufig heraus, dass die Einführung eines deterministischen Einflusses (z. B. durch einen externen Beobachter) bestimmte Eigenschaften des Ergebnisses drastisch verbessern und es für bestimmte praktische Zwecke geeigneter machen kann. Ziel des aktuellen Projekts ist die Untersuchung von Fällen stochastischer Prozesse, die von einem Beobachter gesteuert werden. Konkreter zielt das Projekt darauf ab, mehrere natürliche (kombinatorische und geometrische) Variationen des gut untersuchten Power-of-Two-Choice- Paradigmas zu entwickeln, das wie folgt beschrieben wird. Einem Beobachter werden n zunächst leere Behälter gegeben. Bei jedem Schritt werden ihnen zwei gleichmäßig zufällige Bins vorgeschlagen. Anschließend darf der Beobachter einen Ball in einen der beiden Behälter werfen. Wie sich herausstellt, gelingt es dem Beobachter, die maximale Belastung eines Behälters nach n Schritten im Vergleich zur rein zufälligen (unüberwachten) Einstellung deutlich zu reduzieren. Bei diesem Prozess handelt es sich um ein vereinfachtes stochastisches Modell im Bereich des Lastausgleichs, dessen praktische Anwendungen paralleles Rechnen und Aufgabenplanung umfassen.