Bin packing is the algorithmic problem of packing a collection of items (with scalar sizes) in homogeneous bins of some given size so as to minimize the total number of bins used. It is a fundamental problem that appears as a motif in numerous operations applications. In the stochastic online version of bin packing, items with sizes sampled from an unknown distribution are revealed one at a time and must be irrevocably packed in a bin at the time of arrival. Our focus in this talk will be on online packing algorithms which are oblivious to the distribution of item sizes, while at the same time are optimal asymptotically (as the number of items packed becomes large).

We will survey the development of the literature on online stochastic bin packing, and present our recent results on the first truly distribution-oblivious asymptotically optimal algorithm for this problem. Our proposed algorithm is inspired by an interior-point relaxation of the bin packing linear program. We will also present robustness guarantees for our algorithm against non-i.i.d. input sequences. Finally, we will present extensions to scenarios where items arrive and depart from the system, and the sojourn time of items may depend on the congestion of the bin they are packed in. The goal here is to minimize the steady-state number of occupied bins.

This is joint work with Ana Radovanovic (Google Research).