March 28, Wednesday 14:15, Room 303, Jacobs Building
We study the following balls and bins stochastic process: There is
a buffer with B bins, and a stream of balls X_1, X_2,...,X_T such that X_i is the number of balls that arrive at time i. Once a ball arrives, it is stored in one of the unoccupied bins. If all the bins are occupied then the ball is thrown away. In each time step, we select a bin uniformly at random, clear it, and gain its content. Once the stream of balls ends, all the remaining
balls in the buffer are cleared and added to our gain. We compare the expected gain to the gain of the optimal strategy, which gets the same online stream of balls, and clears a ball from a bin, if exists, at any step.
We name this gain ratio the loss of serving in the dark.
In this paper, we determine the exact loss of serving in the dark. Specifically, it is rho + epsilon where rho is about 1.69996 and epsilon>0 for which B = \Omega(1/\epsilon^3). We also demonstrate that this bound is essentially tight (up to the epsilon which tends to zero). We present an application relating to prompt packets scheduling.
Joint work with Ilan Cohen and Iftah Gamzu