Premium
A stochastic assignment problem
Author(s) -
Wu David T.,
Ross Sheldon M.
Publication year - 2015
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21611
Subject(s) - ball (mathematics) , mathematics , combinatorics , mathematical economics , computer science , binary number , mathematical optimization , operations research , arithmetic , geometry
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