A POWER-OF-TWO-CHOICES UNBALANCED ALLOCATION PROCESS

作者：Redlich Amanda^*

来源：SIAM Journal on Discrete Mathematics, 2017, 31(1): 477-488.

DOI：10.1137/110830988

• Achlioptas process
• differential equations method
• power of two choices
• preferential attachment model
• randomized algorithm

The well-studied "power of two choices" family of algorithms creates balanced allocations of m balls into n bins by, for each ball, selecting a few bins at random and then placing the item in the least-loaded bin. A natural variation is to create an unbalanced allocation by, for each ball, selecting a few bins at random and then placing the ball in the most-loaded bin. Surprisingly, this variation has not been previously studied. This paper introduces this family of unbalanced allocation processes and begins its analysis. The behavior of the bounded m case is analyzed in detail via differential equations and coupling, and some preliminary results for the general case are presented.

• 出版日期2017