A stochastic assignment problem
Abstract
There are n boxes with box i having a quota value Balls arrive sequentially, with each ball having a binary vector attached to it, with the interpretation being that if Xi = 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
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Dec 11, 2014
- Source ID
- 10.1002/nav.21611
Entities
People
- David T. Wu
- Sheldon M. Ross
Organizations
- National Science Foundation
- United States Army Research Laboratory
- University of Southern California