T. Batu; "An Online Chains-into-Bins Process", July 27, 14:40, L027
  • FENS
  • T. Batu; "An Online Chains-into-Bins Process", July 27, 14:40, L027

You are here

Faculty of Engineering and Natural Sciences

An Online Chains-into-Bins Process

Tuğkan Batu
London School of Economics


The study of balls-into-bins games or occupancy problems has a long history. These processes can be used to translate realistic problems into mathematical ones in a natural way. Typically, the goal of a balls-into-bins protocol is to allocate a set of independent objects (tasks, jobs, balls) to a set of resources (servers, bins, urns) and, thereby, to minimize the maximum load.

Here we look at a variant of this protocol and investigate the setting where balls are connected into chains. In particular, we analyse the maximum load for a chains-into-bins protocol where we have $n$ bins and the balls are connected in $m$ chains of length $l$. In this process, the balls of one chain have to be allocated to $l$ consecutive bins. We allow each chain $d$ independent and uniformly random bin choices. The chain is allocated using the rule that the maximum load of any bin receiving a ball of that chain is minimized. We show that, for $d \ge 2$ and $ml=O(n)$, the maximum load is $(\ln\ln m / \ln d) + O(1)$ with probability $1-O(1/m^{d-1})$. The result parallels the corresponding balls-into-bins result and is derived analogously.

Joint work with Petra Berenbrink and Colin Cooper.

Short Bio:

Tugkan Batu received his Ph.D. from Cornell University in 2001. He held Postdoctoral Fellow positions at the University of Pennsylvania, the University of Texas at Austin, and Simon Fraser University. Currently, he is a Lecturer in the Department of Mathematics at the London School of Economics.

July 27, 2009, 14:40, FENS L027