A Generalization of Multiple Choice Balls-into-Bins: Tight Bounds

Gahyun Park

This paper investigates a general version of the multiple choice model called the $(k,d)$-choice process in which $n$ balls are assigned to $n$ bins. In the process, $kn$ balls are placed into $n$ bins, if $d \geq 2k$. Potential applications are also discussed such as distributed storage as well as parallel job scheduling in a cluster.

Knowledge Graph



Sign up or login to leave a comment