Multiple choice allocations with small maximum loads

Abstract

The idea of using multiple choices to improve allocation schemes is now well understood and is often illustrated by the following example. Suppose $n$ balls are allocated to $n$ bins with each ball choosing a bin independently and uniformly at random. The \emph{maximum load}, or the number of balls in the most loaded bin, will then be approximately $\log n \over \log \log n$ with high probability. Suppose now the balls are allocated sequentially by placing a ball in the least loaded bin among the $k\ge 2$ bins chosen independently and uniformly at random. Azar, Broder, Karlin, and Upfal showed that in this scenario, the maximum load drops to ${\log \log n \over \log k} +\Theta(1)$, with high probability, which is an exponential improvement over the previous case. In this thesis we investigate multiple choice allocations from a slightly different perspective. Instead of minimizing the maximum load, we fix the bin capacities and focus on maximizing the number of balls that can be allocated without overloading any bin. In the process that we consider we have $m=\lfloor cn \rfloor$ balls and $n$ bins. Each ball chooses $k$ bins independently and uniformly at random. \emph{Is it possible to assign each ball to one of its choices such that the no bin receives more than $\ell$ balls?} For all $k\ge 3$ and $\ell\ge 2$ we give a critical value, $c_{k,\ell}^*$, such that when $c<c_{k,\ell}^*$ an allocation is possible with high probability and when $c>c_{k,\ell}^*$ this is not the case. In case such an allocation exists, \emph{how quickly can we find it?} Previous work on total allocation time for case $k\ge 3$ and $\ell=1$ has analyzed a \emph{breadth first strategy} which is shown to be linear only in expectation. We give a simple and efficient algorithm which we also call \emph{local search allocation}(LSA) to find an allocation for all $k\ge 3$ and $\ell=1$. Provided the number of balls are below (but arbitrarily close to) the theoretical achievable load threshold, we give a \emph{linear} bound for the total allocation time that holds with high probability. We demonstrate, through simulations, an order of magnitude improvement for total and maximum allocation times when compared to the state of the art method. Our results find applications in many areas including hashing, load balancing, data management, orientability of random hypergraphs and maximum matchings in a special class of bipartite graphs.

Die Idee, mehrere Wahlmöglichkeiten zu benutzen, um Zuordnungsschemas zu verbessern, ist mittlerweile gut verstanden und wird oft mit Hilfe des folgenden Beispiels illustriert: Man nehme an, dass n Kugeln auf n Behälter verteilt werden und jede Kugel unabhängig und gleichverteilt per Zufall ihren Behälter wählt. Die maximale Auslastung, bzw. die Anzahl an Kugeln im meist befüllten Behälter, wird dann mit hoher Wahrscheinlichkeit schätzungsweise $\log n \over \log \log n$ sein. Alternativ können die Kugeln sequenziell zugeordnet werden, indem jede Kugel k ≥ 2 Behälter unabhängig und gleichverteilt zufällig auswählt und in dem am wenigsten befüllten dieser k Behälter platziert wird. Azar, Broder, Karlin, and Upfal haben gezeigt, dass in diesem Szenario die maximale Auslastung mit hoher Wahrscheinlichkeit auf ${\log \log n \over \log k} +\Theta(1)$ sinkt, was eine exponentielle Verbesserung des vorhergehenden Falls darstellt. In dieser Doktorarbeit untersuchen wir solche Zuteilungschemas von einem etwas anderen Standpunkt. Statt die maximale Last zu minimieren, fixieren wir die Kapazitäten der Behälter und konzentrieren uns auf die Maximierung der Anzahl der Kugeln, die ohne Überlastung eines Behälters zugeteilt werden können. In dem von uns betrachteten Prozess haben wir m = bcnc Kugeln und n Behälter. Jede Kugel wählt unabhängig und gleichverteilt zufällig k Behälter. Ist es möglich, jeder Kugel einen Behälter ihrer Wahl zuzuordnen, so dass kein Behälter mehr als Kugeln erhält? Für alle k ≥ 3 und ≥ 2 geben wir einen kritischen Wert $c _{k,\ell}^*$, an sodass für c < c {k,\ell}^*$ eine Zuordnung mit hoher Wahrscheinlich möglich ist und für c > c {k,\ell}^*$ nicht. Im Falle, dass solch eine Zuordnung existiert, stellt sich die Frage, wie schnell diese gefunden werden kann. Die bisher durchgeführten Arbeiten zur Gesamtzuordnungszeit im Falle k ≥ 3 and $\ell = 1$ haben eine Breitensuchstrategie analysiert, welche nur im Erwartungswert linear ist. Wir präsentieren einen einfachen und effizienten Algorithmus, welchen wir local search allocation (LSA) nennen und der Zuteilungen für alle k ≥ 3 und $\ell = 1$ findet. Sofern die Anzahl der Kugeln unter (aber beliebig nahe an) der theoretisch erreichbaren Lastschwelle ist, zeigen wir eine lineare Schranke für die Gesamtzuordnungszeit, die mit hoher Wahrscheinlichkeit gilt. Anhand von Simulationen demonstrieren wir eine Verbesserung der Gesamt- und Maximalzuordnungszeiten um eine Größenordnung im Vergleich zu anderen aktuellen Methoden. Unsere Ergebnisse finden Anwendung in vielen Bereichen einschließlich Hashing, Lastbalancierung, Datenmanagement, Orientierbarkeit von zufälligen Hypergraphen und maximale Paarungen in einer speziellen Klasse von bipartiten Graphen.