IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v62y2015i1p23-31.html
   My bibliography  Save this article

A stochastic assignment problem

Author

Listed:
  • David T. Wu
  • Sheldon M. Ross

Abstract

There are n boxes with box i having a quota value m 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 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

Suggested Citation

  • David T. Wu & Sheldon M. Ross, 2015. "A stochastic assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(1), pages 23-31, February.
    • Handle: RePEc:wly:navres:v:62:y:2015:i:1:p:23-31
    DOI: 10.1002/nav.21611
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.21611
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.21611?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Anton J. Kleywegt & Jason D. Papastavrou, 2001. "The Dynamic and Stochastic Knapsack Problem with Random Sized Items," Operations Research, INFORMS, vol. 49(1), pages 26-41, February.
    2. Cyrus Derman & Gerald J. Lieberman & Sheldon M. Ross, 1972. "A Sequential Stochastic Assignment Problem," Management Science, INFORMS, vol. 18(7), pages 349-355, March.
    3. Stefanos A. Zenios & Glenn M. Chertow & Lawrence M. Wein, 2000. "Dynamic Allocation of Kidneys to Candidates on the Transplant Waiting List," Operations Research, INFORMS, vol. 48(4), pages 549-569, August.
    4. David, Israel & Levi, Ofer, 2004. "A new algorithm for the multi-item exponentially discounted optimal selection problem," European Journal of Operational Research, Elsevier, vol. 153(3), pages 782-789, March.
    5. S. Christian Albright, 1974. "Optimal Sequential Assignments with Random Arrival Times," Management Science, INFORMS, vol. 21(1), pages 60-67, September.
    6. Sheldon Ross & David Wu, 2013. "A generalized coupon collecting model as a parsimonious optimal stochastic assignment model," Annals of Operations Research, Springer, vol. 208(1), pages 133-146, September.
    7. Alexander G. Nikolaev & Sheldon H. Jacobson, 2010. "Technical Note ---Stochastic Sequential Decision-Making with a Random Number of Jobs," Operations Research, INFORMS, vol. 58(4-part-1), pages 1023-1027, August.
    8. Xuanming Su & Stefanos A. Zenios, 2005. "Patient Choice in Kidney Allocation: A Sequential Stochastic Assignment Model," Operations Research, INFORMS, vol. 53(3), pages 443-455, June.
    9. Chris Albright & Cyrus Derman, 1972. "Asymptotic Optimal Policies for the Stochastic Sequential Assignment Problem," Management Science, INFORMS, vol. 19(1), pages 46-51, September.
    10. D. P. Kennedy, 1986. "Optimal Sequential Assignment," Mathematics of Operations Research, INFORMS, vol. 11(4), pages 619-626, November.
    11. Chun, Young H. & Sumichrast, Robert T., 2006. "A rank-based approach to the sequential selection and assignment problem," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1338-1344, October.
    12. C. Derman & G. J. Lieberman & S. M. Ross, 1975. "A Stochastic Sequential Allocation Model," Operations Research, INFORMS, vol. 23(6), pages 1120-1130, December.
    13. S. Christian Albright, 1974. "A Markov-Decision-Chain Approach to a Stochastic Assignment Problem," Operations Research, INFORMS, vol. 22(1), pages 61-64, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Meghan Shanks & Ge Yu & Sheldon H. Jacobson, 2023. "Approximation algorithms for stochastic online matching with reusable resources," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 98(1), pages 43-56, August.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Arash Khatibi & Sheldon H. Jacobson, 2016. "Doubly Stochastic Sequential Assignment Problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(2), pages 124-137, March.
    2. Alexander G. Nikolaev & Sheldon H. Jacobson, 2010. "Technical Note ---Stochastic Sequential Decision-Making with a Random Number of Jobs," Operations Research, INFORMS, vol. 58(4-part-1), pages 1023-1027, August.
    3. Sheldon M. Ross & Gideon Weiss & Zhengyu Zhang, 2021. "Technical Note—A Stochastic Assignment Problem with Unknown Eligibility Probabilities," Operations Research, INFORMS, vol. 69(1), pages 266-272, January.
    4. Xuanming Su & Stefanos A. Zenios, 2005. "Patient Choice in Kidney Allocation: A Sequential Stochastic Assignment Model," Operations Research, INFORMS, vol. 53(3), pages 443-455, June.
    5. Xuhan Tian & Junmin (Jim) Shi & Xiangtong Qi, 2022. "Stochastic Sequential Allocations for Creative Crowdsourcing," Production and Operations Management, Production and Operations Management Society, vol. 31(2), pages 697-714, February.
    6. Tianke Feng & Joseph C. Hartman, 2015. "The dynamic and stochastic knapsack Problem with homogeneous‐sized items and postponement options," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(4), pages 267-292, June.
    7. Meghan Shanks & Ge Yu & Sheldon H. Jacobson, 2023. "Approximation algorithms for stochastic online matching with reusable resources," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 98(1), pages 43-56, August.
    8. Baris Ata & Yichuan Ding & Stefanos Zenios, 2021. "An Achievable-Region-Based Approach for Kidney Allocation Policy Design with Endogenous Patient Choice," Manufacturing & Service Operations Management, INFORMS, vol. 23(1), pages 36-54, 1-2.
    9. Sheldon Ross & David Wu, 2013. "A generalized coupon collecting model as a parsimonious optimal stochastic assignment model," Annals of Operations Research, Springer, vol. 208(1), pages 133-146, September.
    10. David, Israel & Levi, Ofer, 2004. "A new algorithm for the multi-item exponentially discounted optimal selection problem," European Journal of Operational Research, Elsevier, vol. 153(3), pages 782-789, March.
    11. Arash Khatibi & Golshid Baharian & Banafsheh Behzad & Sheldon Jacobson, 2015. "Extensions of the sequential stochastic assignment problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 82(3), pages 317-340, December.
    12. C G Lennon & J M McGowan & K Y Lin, 2008. "A game-theoretic model for repeated assignment problem between two selfish agents," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(12), pages 1652-1658, December.
    13. Yizhaq Minchuk & Aner Sela, 2018. "Asymmetric sequential search under incomplete information," Journal of Economics & Management Strategy, Wiley Blackwell, vol. 27(2), pages 315-325, June.
    14. , & , & ,, 2011. "Revenue maximization in the dynamic knapsack problem," Theoretical Economics, Econometric Society, vol. 6(2), May.
    15. Yael Deutsch & Israel David, 2020. "Benchmark policies for utility-carrying queues with impatience," Queueing Systems: Theory and Applications, Springer, vol. 95(1), pages 97-120, June.
    16. Michael Katehakis & Ingram Olkin & Sheldon Ross & Jian Yang, 2013. "On the life and work of Cyrus Derman," Annals of Operations Research, Springer, vol. 208(1), pages 5-26, September.
    17. Adrian Lee & Sheldon Jacobson, 2011. "Sequential stochastic assignment under uncertainty: estimation and convergence," Statistical Inference for Stochastic Processes, Springer, vol. 14(1), pages 21-46, February.
    18. Hak Chun, Young, 1996. "Selecting the best choice in the weighted secretary problem," European Journal of Operational Research, Elsevier, vol. 92(1), pages 135-147, July.
    19. Golshid Baharian & Sheldon H. Jacobson, 2013. "Limiting behavior of the stochastic sequential assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(4), pages 321-330, June.
    20. Sahar Ahmadvand & Mir Saman Pishvaee, 2018. "An efficient method for kidney allocation problem: a credibility-based fuzzy common weights data envelopment analysis approach," Health Care Management Science, Springer, vol. 21(4), pages 587-603, December.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:62:y:2015:i:1:p:23-31. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.