文章基本信息

标题：The power of thinning in balanced allocation
本地全文：下载
作者：Ohad N. Feldheim ; Ori Gurel-Gurevich
期刊名称：Electronic Communications in Probability
印刷版ISSN：1083-589X
出版年度：2021
卷号：26
页码：1-8
DOI：10.1214/21-ECP400
语种：English
出版社：Electronic Communications in Probability
摘要：Balls are sequentially allocated into n bins as follows: for each ball, an independent, uniformly random bin is generated. An overseer may then choose to either allocate the ball to this bin, or else the ball is allocated to a new independent uniformly random bin. The goal of the overseer is to reduce the load of the most heavily loaded bin after Θ(n) balls have been allocated. We provide an asymptotically optimal strategy yielding a maximum load of (1+o(1)) 8logn loglogn balls.
关键词：(1+α)-choice; 60C05; 68W27; balanced allocation; load balancing;balls and bins; one-retry; subsampling; thinning; two-choices