The Online Stochastic Generalized Assignment Problem
We present a (1 \frac{1}\sqrt{k} competitive algorithm for the online stochastic generalized assignment problem under the assumption that no item takes up more than \frac{1}{k} fraction of the capacity of any bin. Items arrive online; each item has a value and a size; upon arrival, an item can be placed in a bin or discarded; the objective is to maximize the total value of the placement. Both value and size of an item may depend on the bin in which the item is placed; the size of an item is revealed only after it has been placed in a bin; distribution information is available about the value and size of each item in advance (not necessarily i.i.d) however items arrive in adversarial order (non adaptive adversary)
APPROX RANDOM