I was recently helping a friend move. I stood in the moving truck as other people brought boxes and furniture pieces from inside the house. My job was to arrange these items in an efficient way inside the truck. I had no idea what the size or shape of the next object would be. But as more objects came, I had a rough idea of the average shape and size of the boxes and containers in the house, and I could develop an expected size and shape for the next object. I wonder, is there an algorithm for this type of problem. Formally, I think the problem would be worded like this:
Let $X$ be a set of $m$-dimensional geometric objects of unknown size and shape, and let $S\subset\mathbb R^m$ be bounded. Suppose that $n-1$ objects are randomly selected from $X$, and arranged in a non-overlapping manner in $S$. Suppose that an $n^\text{th}$ object is randomly selected from $X$ (so that this object's size and shape are now known). What is the optimal way to place this object in $S$ so that as many randomly selected objects from $X$ may be placed in $S$ as possible in the future?
If this problem is far too general, it may be assumed that all of the geometric objects are rectangular prisms, and that $m=3$.
I am not familiar with solving this type of problem. Is there a theorem, algorithm, or technique which relates to this situation?
The problem is NP-hard in any natural version, so approximation algorithms are necessary. Some of the key phrases in this area are "bin-packing," modified with "best-fit," "first-fit," "next fit," and "random-order." In particular, the 2nd paper below analyzes the random-order performance of Next Fit, which is close to your procedure.
The packing literature is vast and I am not an expert. But I believe the overall conclusion is that one can achieve $2 \times$ optimal performance.