Order of decay of the wasted space for a stochastic packing problem. (Q1884829)

This paper considers successive packing in the unit square of random rectangles with the additional property (called ``simple'' in the paper) that each vertical line drawn in the square can intersect at most one rectangle. The main result states that \[ \log E(W_N) \geq -\tfrac12\log N + K \sqrt{\log N}, \] for large enough \(N\) and some constant \(K>0\). In a separate paper the author [Int. J. Comput. Math. 76, No. 4, 479--488 (2001; Zbl 0986.60012)] also proved the upper bound \[ \log E(W_N) \leq -\frac12 \log N + O(\sqrt{\log N}). \] Recently, \textit{M. Talagrand} [Expected wasted space of optimal simple rectangle packing, Probab. Theory Relat. Fields (in press)] improved the above results by showing that \[ \log E(W_n) = -\tfrac12\log N + \sqrt{\log 2\log N} +O(\log\log N), \] where the implied constant in the \(O\)-symbol is less than \(1/2\).