Balanced allocation and dictionaries with tightly packed constant size bins

AbstractWe study a particular aspect of the balanced allocation paradigm (also known as the “two-choices paradigm”): constant sized bins, packed as tightly as possible. Let d≥1 be fixed, and assume there are m bins of capacity d each. To each of n≤dm balls two possible bins are assigned at random. How close can dm/n=1+ε be to 1 so that with high probability each ball can be put into one of the two bins assigned to it without any bin overflowing? We show that ε>(2/e)d−1 is sufficient. If a new ball arrives with two new randomly assigned bins, we wish to rearrange some of the balls already present in order to accommodate the new ball. We show that on average it takes constant time to rearrange the balls to achieve this, for ε>βd, for some constant β