On the asymptotic optimality of first-fit storage allocation.

Suppose intervals arrive in a Poisson stream at rate 1 and each interval remains independently for an exponential time with mean 1/rho. The lengths of the intervals are assumed to be independent with common distribution F. As each interval arrives, it is placed as far to the left as possible on the real line [0,infinity) without overlapping the intervals already there. This is the so-called first-fit storage discipline. We conjecture that first fit is is asymptotically optimal in the sense that the ratio of expected empty space to expected occupied space tend to zero as rho 0, i.e. as the occupied space tends to infinity. This conjecture seems very hard to prove, but it has been proved for constant interval lengths, i.e. when F degenerates.