IDEAS home Printed from https://ideas.repec.org/p/mit/sloanp/2530.html
   My bibliography  Save this paper

Restless bandit, linear programming relaxations and a primal-dual heuristic

Author

Listed:
  • Bertsimas, Dimitris.
  • Niño-Mora, Jose.

Abstract

Includes bibliographical references (p. 19-21).

Suggested Citation

  • Bertsimas, Dimitris. & Niño-Mora, Jose., 1994. "Restless bandit, linear programming relaxations and a primal-dual heuristic," Working papers 3727-94., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    • Handle: RePEc:mit:sloanp:2530
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/1721.1/2530
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. A. Federgruen & H. Groenevelt, 1988. "M/G/c Queueing Systems with Multiple Customer Classes: Characterization and Control of Achievable Performance Under Nonpreemptive Priority Rules," Management Science, INFORMS, vol. 34(9), pages 1121-1138, September.
    2. A. Federgruen & H. Groenevelt, 1988. "Characterization and Optimization of Achievable Performance in General Queueing Systems," Operations Research, INFORMS, vol. 36(5), pages 733-741, October.
    3. E. G. Coffman & I. Mitrani, 1980. "A Characterization of Waiting Time Performance Realizable by Single-Server Queues," Operations Research, INFORMS, vol. 28(3-part-ii), pages 810-821, June.
    4. Jonathan P. Caulkins, 1993. "Local Drug Markets' Response to Focused Police Enforcement," Operations Research, INFORMS, vol. 41(5), pages 848-863, October.
    5. Bertsimas, Dimitris., 1994. "A mathematical programming approach to stochastic and dynamic optimization problems," Working papers 3668-94., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    6. J. George Shanthikumar & David D. Yao, 1992. "Multiclass Queueing Systems: Polymatroidal Structure and Optimal Scheduling Control," Operations Research, INFORMS, vol. 40(3-supplem), pages 293-299, June.
    7. Bertsimas, Dimitris & Teo, Chungpiaw., 1994. "From valid inequalities to heuristics : a unified view of primal-dual approximation algortithms [sic] in covering problems," Working papers 3707-94., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    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. Dimitris Bertsimas & José Niño-Mora, 1996. "Optimization of multiclass queueing networks with changeover times via the achievable region method: Part II, the multi-station case," Economics Working Papers 314, Department of Economics and Business, Universitat Pompeu Fabra, revised Aug 1998.
    2. Dimitris Bertsimas & José Niño-Mora, 1999. "Optimization of Multiclass Queueing Networks with Changeover Times Via the Achievable Region Approach: Part II, The Multi-Station Case," Mathematics of Operations Research, INFORMS, vol. 24(2), pages 331-361, May.
    3. Bertsimas, Dimitris., 1995. "The achievable region method in the optimal control of queueing systems : formulations, bounds and policies," Working papers 3837-95., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    4. Dimitris Bertsimas & José Niño-Mora, 1996. "Optimization of multiclass queueing networks with changeover times via the achievable region approach: Part I, the single-station case," Economics Working Papers 302, Department of Economics and Business, Universitat Pompeu Fabra, revised Jul 1998.
    5. José Niño-Mora, 1999. "Restless bandits, partial conservation laws and indexability," Economics Working Papers 435, Department of Economics and Business, Universitat Pompeu Fabra.

    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. Tianhu Deng & Ying‐Ju Chen & Zuo‐Jun Max Shen, 2015. "Optimal pricing and scheduling control of product shipping," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(3), pages 215-227, April.
    2. José Niño-Mora, 2006. "Restless Bandit Marginal Productivity Indices, Diminishing Returns, and Optimal Control of Make-to-Order/Make-to-Stock M/G/1 Queues," Mathematics of Operations Research, INFORMS, vol. 31(1), pages 50-84, February.
    3. Bertsimas, Dimitris., 1995. "The achievable region method in the optimal control of queueing systems : formulations, bounds and policies," Working papers 3837-95., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    4. Hellerstein, Lisa & Lidbetter, Thomas, 2023. "A game theoretic approach to a problem in polymatroid maximization," European Journal of Operational Research, Elsevier, vol. 305(2), pages 979-988.
    5. José Niño-Mora, 2000. "On certain greedoid polyhedra, partially indexable scheduling problems and extended restless bandit allocation indices," Economics Working Papers 456, Department of Economics and Business, Universitat Pompeu Fabra.
    6. Dimitris Bertsimas & José Niño-Mora, 1996. "Optimization of multiclass queueing networks with changeover times via the achievable region approach: Part I, the single-station case," Economics Working Papers 302, Department of Economics and Business, Universitat Pompeu Fabra, revised Jul 1998.
    7. Dimitris Bertsimas & Velibor V. Mišić, 2016. "Decomposable Markov Decision Processes: A Fluid Optimization Approach," Operations Research, INFORMS, vol. 64(6), pages 1537-1555, December.
    8. Shaler Stidham, 2002. "Analysis, Design, and Control of Queueing Systems," Operations Research, INFORMS, vol. 50(1), pages 197-216, February.
    9. Dimitris Bertsimas & José Niño-Mora, 2000. "Restless Bandits, Linear Programming Relaxations, and a Primal-Dual Index Heuristic," Operations Research, INFORMS, vol. 48(1), pages 80-90, February.
    10. Dimitris Bertsimas & José Niño-Mora, 1996. "Optimization of multiclass queueing networks with changeover times via the achievable region method: Part II, the multi-station case," Economics Working Papers 314, Department of Economics and Business, Universitat Pompeu Fabra, revised Aug 1998.
    11. Esther Frostig & Gideon Weiss, 2016. "Four proofs of Gittins’ multiarmed bandit theorem," Annals of Operations Research, Springer, vol. 241(1), pages 127-165, June.
    12. Dimitris Bertsimas & José Niño-Mora, 1994. "Restless bandits, linear programming relaxations and a primal-dual index heuristic," Economics Working Papers 301, Department of Economics and Business, Universitat Pompeu Fabra, revised Oct 1997.
    13. 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.
    14. José Niño-Mora, 2020. "A Verification Theorem for Threshold-Indexability of Real-State Discounted Restless Bandits," Mathematics of Operations Research, INFORMS, vol. 45(2), pages 465-496, May.
    15. Vanlerberghe, Jasper & Walraevens, Joris & Maertens, Tom & Bruneel, Herwig, 2018. "Calculation of the performance region of an easy-to-optimize alternative for Generalized Processor Sharing," European Journal of Operational Research, Elsevier, vol. 270(2), pages 625-635.
    16. Veeraruna Kavitha & Jayakrishnan Nair & Raman Kumar Sinha, 2019. "Pseudo conservation for partially fluid, partially lossy queueing systems," Annals of Operations Research, Springer, vol. 277(2), pages 255-292, June.
    17. R. Garbe & K. D. Glazebrook, 1998. "Submodular Returns and Greedy Heuristics for Queueing Scheduling Problems," Operations Research, INFORMS, vol. 46(3), pages 336-346, June.
    18. Santiago R. Balseiro & Ozan Candogan, 2017. "Optimal Contracts for Intermediaries in Online Advertising," Operations Research, INFORMS, vol. 65(4), pages 878-896, August.
    19. Muhammad El-Taha, 2016. "Invariance of workload in queueing systems," Queueing Systems: Theory and Applications, Springer, vol. 83(1), pages 181-192, June.
    20. José Niño-Mora, 2022. "Multi-Gear Bandits, Partial Conservation Laws, and Indexability," Mathematics, MDPI, vol. 10(14), pages 1-31, July.

    More about this item

    Keywords

    HD28 .M414 no.3727-; 94;

    JEL classification:

    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:mit:sloanp:2530. 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: None (email available below). General contact details of provider: https://edirc.repec.org/data/ssmitus.html .

    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.