Online Stochastic Bin Packing

Understand

Bin packing is an algorithmic problem that arises in diverse applications such as remnant inventory systems, shipping logistics, and appointment scheduling.

• In its simplest variant, a sequence of $T$ items (e.g., orders for raw material, packages for delivery) is revealed one at a time, and each item must be packed on arrival in an available bin (e.g., remnant pieces of raw material in inventory, shipping containers).
• The sizes of items are i.i.d.
• samples from an unknown distribution, but the sizes are known when the items arrive.