  Consider a storage area where arriving items are stored temporarily in
bounded capacity stacks until their departure. We look into the problem of
deciding where to put an arriving item with the objective of minimizing the
maximum number of stacks used over time. The decision has to be made as soon as
an item arrives, and we assume that we only have information on the departure
times for the arriving item and the items currently at the storage area. We are
only allowed to put an item on top of another item if the item below departs at
a later time. We refer to this problem as online stacking. We assume that the
storage time intervals are picked i.i.d. from $[0, 1] \times [0, 1]$ using an
unknown distribution with a bounded probability density function. Under this
mild condition, we present a simple polynomial time online algorithm and show
that the competitive ratio converges to $1$ in probability. The result holds if
the stack capacity is $o(\sqrt{n})$, where $n$ is the number of items,
including the realistic case where the capacity is a constant. Our experiments
show that our results also have practical relevance. To the best of our
knowledge, we are the first to present an asymptotically optimal algorithm for
online stacking, which is an important problem with many real-world
applications within computational logistics.
