# Two-Way Linear Probing Revisited
## 2 Background and History
### The Multiple-Choice Paradigm  
Allocating balls into bins is one of the historical assignment problems [71; 72]. We are given \(r\) balls that have to be placed into \(s\) bins. The balls have to be inserted sequentially and on-line, that is, each ball is assigned upon arrival without knowing anything about the future coming balls. The _load of a bin_ is defined to be the number of balls it contains. We would like to design an allocation process that minimizes the maximum load among all bins upon termination. For example, in a classical allocation process, each ball is placed into a bin chosen independently and uniformly at random, with replacement. It is known [73; 74; 75; 44] that, if \(r=\Theta(s)\), the maximum load upon termination is asymptotic to \(\log s/\log\log s\), in probability. On the other hand, the _greedy multiple-choice allocation process_, which appeared in [76; 77] and studied by [PERSON] et al. [10], inserts each ball into the least loaded bin among \(d\geq 2\) bins chosen independently and uniformly at random, with replacement, breaking ties randomly. Throughout, we will refer to this process as \(\textsc{GreedyMC}(s,r,d)\) for inserting \(r\) balls into \(s\) bins. Surprisingly, the maximum bin load of \(\textsc{GreedyMC}(s,s,d)\) decreases exponentially to \(\log_{d}\log s\pm O(1)\), w.h.p., [10]. However, one can easily generalize this to the case \(r=\Theta(s)\). It is also known that the greedy strategy is stochastically optimal in the following sense. **Theorem 1** ([PERSON] et al. [10]). : _Let \(s,r,d\in\mathbb{N}\), where \(d\geq 2\), and \(r=\Theta(s)\). Upon termination of \(\textsc{GreedyMC}(s,r,d)\), the maximum bin load is \(\log_{d}\log s\pm O(1)\), w.h.p. Furthermore, the maximum bin load of any on-line allocation process that inserts \(r\) balls sequentially into \(s\) bins where each ball is inserted into a bin among \(d\) bins chosen independently and uniformly at random, with replacement, is at least \(\log_{d}\log s-O(1)\), w.h.p._  
[PERSON] et al. [14] extended Theorem 1 to the heavily loaded case where \(r\gg s\), and recorded the following tight result. **Theorem 2** ([PERSON] et al. [14]). : _There is a constant \(C>0\) such that, for any integers \(r\geq s>0\), and \(d\geq 2\), the maximum bin load upon termination of the process \(\textsc{GreedyMC}(s,r,d)\) is \(\log_{d}\log s+r/s\pm C\), w.h.p._  
Theorem 2 is a crucial result that we have used to derive our results; see Theorems 8 and 9. It states that the deviation from the average bin load, which is \(\log_{d}\log s\), stays unchanged as the number of balls increases. [PERSON] [11; 78] demonstrated that it is possible to improve the performance of the greedy process, if non-uniform distributions on the bins and a tie-breaking rule are carefully chosen. He suggested the following variant, which is called _Always-Go-Left_. The bins are numbered from \(1\) to \(n\). We partition the \(s\) bins into \(d\) groups of almost equal size, that is, each group has size \(\Theta(s/d)\). We allow each ball to select upon arrival \(d\) bins independently at random, but the \(i\)-th bin must be chosen uniformly from the \(i\)-th group. Each ball is placed on-line, as before, in the least full bin, but upon a tie, the ball is always placed in the leftmost bin among the \(d\) bins. We shall write \(\textsc{LeftMC}(s,r,d)\) to refer to this process. Vocking [11] showed that, if \(r=\Theta(s)\), the maximum load of \(\textsc{LeftMC}(s,r,d)\) is \(\log\log s/(d\log\phi_{d})+O(1)\), w.h.p., where \(\phi_{d}\) is a constant related to a generalized Fibonaccisequence. For example, the constant \(\phi_{2}=1.61...\) corresponds to the well-known golden ratio, and \(\phi_{3}=1.83\). In general, \(\phi_{2}<\phi_{3}<\phi_{4}<\cdots<2\), and \(\lim_{d\to\infty}\phi_{d}=2\). Observe the improvement on the performance of GreedyMC\((s,r,d)\), even for \(d=2\). The maximum load of LeftMC\((s,r,2)\) is \(0.72...\times\log_{2}\log s+O(1)\), whereas in GreedyMC\((s,r,2)\), it is \(\log_{2}\log s+O(1)\).