Choice-memory tradeoff in allocations (Q990388)

The paper focuses on the balls-and-bins paradigm which describes the process where \(b\) balls are placed independently and uniformly at random in \(n\) bins. The authors study the above models in the presence of constraint on the memory that the online algorithm has at its disposal. They find that a tradeoff between the choice and the memory governs the ability to achieve a perfect allocation as well as a constant maximal load.