Balanced Allocations

摘要: Suppose that we sequentially place $n$ balls into n boxes by putting each ball a randomly chosen box. It is well known when are done, the fullest box has with high probability (1 + o(1))ln n/ln ln in it. instead for choose two at random and one which less full time of placement. We show probability, contains only 2 O(1) balls---exponentially than before. Furthermore, similar gap exists infinite process, where step ball, uniformly random, deleted, added manner above. discuss consequences this related theorems dynamic resource allocation, hashing, on-line load balancing.