Stochastic Analysis of a Modified First Fit Decreasing Packing

We make a stochastic analysis of a modified version mFFD of First Fit Decreasing, in which each bin is closed after it receives its first fallback item. Consider a probability measure μ on [0, 1], and independent random variables X₁, …, X_n distributed according to μ. Let R_n = R(X₁, …, X_n) be the number of unit size bins that mFFD needs to pack items of size X₁, …, X_n. We prove that c(μ) = lim_n→∞E(R_n)/n exists and that the random variable (R_n − nc(μ))/√n converges in distribution. The main tools are deterministic inequalities concerning mFFD, that might be of independent interest.