Skip to main content
  • Gahyun Park - A Generalization of Multiple Choice Balls-into-Bins

  • Monday, October 24, 2011 2:00 PM - 3:00 PM EDT
    LWSN 3012
    Purdue University

    Presentation by guest speaker: Gahyun Park, Assistant Professor of Computer Science at SUNY Geneseo

    In the singe choice balls into bins problem, a ball is placed into a bin chosen independently and uniformly at random ({\\it i.u.r.}) It is well known that the maximum load after $n$ balls are placed into $n$ bins is at most $(1+o(1))(\\log n/\\log \\log n)$ with high probability. In the multiple choice paradigm, also known as $d$-choice, each ball is placed into the least loaded one out of $d>1$ bins chosen {\\it i.u.r.} The maximum load in the $d$-choice is dramatically reduced to $\\ln\\ln n/\\ln d + O(1)$.

    In this work, we propose the following $(k,d)$-choice process. For $k