LONG-TERM BALANCED ALLOCATION VIA THINNING

• 成果类型: Article
• 署名作者: Feldheim, Ohad Noy; Gurel-Gurevich, Ori; Li, Jiange
• 署名单位: Hebrew University of Jerusalem; Harbin Institute of Technology
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/23-AAP1978
• 发表日期: 2024
• 页码: 795-850
• 关键词: balls

摘要

In the two-thinning balls-and-bins model, an overseer is provided with uniform random allocation of m balls into n bins in an on-line fashion. The overseer may reject the allocation of each ball, in which case it is placed into a new bin, drawn independently, uniformly at random. The purpose of the overseer is to reduce the maximum load, that is, the difference between the maximum number of balls in a single bin and the average number of balls among all bins. We provide tight estimates for three quantities: the lowest achievable maximum load at a given time m, the lowest achievable maximum load uniformly over the entire time interval [m] := {1, 2,..., m} and the lowest achievable typical maximum load over the interval [m], that is, a load which upperbounds 1 - o(1) portion of the times in [m]. In particular, for m polynomial in n and sufficiently large, we provide an,explicit strategy, which achieves a typical maximum load of (logn)(1/2+o(1)) asymptotically the same as that can be achieved at a single time m. In contrast, log we show that no strategy can achieve better than Theta(logn/log log n) maximum load for all times up to time m.