Item

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 \emphmaximum 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≥ 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 ℓ balls?} For all k≥ 3
and ℓ≥ 2 we give a critical value, c_{k,ℓ}^*, such that when
cc_{k,ℓ}^* 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≥ 3 and ℓ=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≥ 3 and ℓ=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.