BALANCED ALLOCATION: MEMORY PERFORMANCE TRADEOFFS
成果类型：
Article
署名作者：
Benjamin, Itai; Makarychev, Yury
署名单位：
Weizmann Institute of Science; Toyota Technological Institute - Chicago
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
DOI：
10.1214/11-AAP804
发表日期：
2012
页码：
1642-1649
关键词：
摘要：
Suppose we sequentially put n balls into n bins. If we put each ball into a random bin then the heaviest bin will contain similar to log n/log log n balls with high probability. However, Azar, Broder, Karlin and Upfal [SIAM J. Comput. 29 (1999) 180-200] showed that if each time we choose two bins at random and put the ball in the least loaded bin among the two, then the heaviest bin will contain only similar to log log n balls with high probability. How much memory do we need to implement this scheme? We need roughly log log log n bits per bin, and n log log log n bits in total. Let us assume now that we have limited amount of memory. For each ball, we are given two random bins and we have to put the ball into one of them. Our goal is to minimize the load of the heaviest bin. We prove that if we have n(1-delta) bits then the heaviest bin will contain at least Omega(delta log n/log log n) balls with high probability. The bound is tight in the communication complexity model.