A stochastic assignment problem

There are n boxes with box i having a quota valuem i , i = 1 … n . Balls arrive sequentially, with each ball having a binary vector X = ( X 1 , X 2 , … , X n ) attached to it, with the interpretation being that if X i  = 1 then that ball is eligible to be put in box i . A ball's vector is revealed when it arrives and the ball can be put in any alive box for which it is eligible, where a box is said to be alive if it has not yet met its quota. Assuming that the components of a vector are independent, we are interested in the policy that minimizes, either stochastically or in expectation, the number of balls that need arrive until all boxes have met their quotas. © 2014 Wiley Periodicals, Inc. 62:23–31, 2015