IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v54y2008i4p763-776.html
   My bibliography  Save this article

A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem

Author

Listed:
  • Retsef Levi

    () (Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Robin Roundy

    () (School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853)

  • David Shmoys

    () (School of Operations Research and Information Engineering and Department of Computer Science, Cornell University, Ithaca, New York 14853)

  • Maxim Sviridenko

    () (IBM T. J. Watson Research Center, Yorktown Heights, New York 10598)

Abstract

Deterministic inventory theory provides streamlined optimization models that attempt to capture trade-offs in managing the flow of goods through a supply chain. We will consider two well-studied deterministic inventory models, called the one-warehouse multiretailer (OWMR) problem and its special case the joint replenishment problem (JRP), and give approximation algorithms with worst-case performance guarantees. That is, for each instance of the problem, our algorithm produces a solution with cost that is guaranteed to be at most 1.8 times the optimal cost; this is called a 1.8-approximation algorithm. Our results are based on an LP-rounding approach; we provide the first constant approximation algorithm for the OWMR problem and improve the previous results for the JRP.

Suggested Citation

  • Retsef Levi & Robin Roundy & David Shmoys & Maxim Sviridenko, 2008. "A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem," Management Science, INFORMS, vol. 54(4), pages 763-776, April.
  • Handle: RePEc:inm:ormnsc:v:54:y:2008:i:4:p:763-776
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.1070.0781
    Download Restriction: no

    References listed on IDEAS

    as
    1. Leroy B. Schwarz, 1973. "A Simple Continuous Review Deterministic One-Warehouse N-Retailer Inventory Problem," Management Science, INFORMS, vol. 19(5), pages 555-566, January.
    2. Awi Federgruen & Michal Tzur, 1991. "A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) Time," Management Science, INFORMS, vol. 37(8), pages 909-925, August.
    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. Danny Segev, 2014. "An Approximate Dynamic-Programming Approach to the Joint Replenishment Problem," Mathematics of Operations Research, INFORMS, vol. 39(2), pages 432-444, May.
    2. repec:spr:mathme:v:88:y:2018:i:3:d:10.1007_s00186-018-0642-4 is not listed on IDEAS
    3. Jesus Cunha & Rafael Melo, 2016. "On reformulations for the one-warehouse multi-retailer problem," Annals of Operations Research, Springer, vol. 238(1), pages 99-122, March.
    4. Sainathuni, Bhanuteja & Parikh, Pratik J. & Zhang, Xinhui & Kong, Nan, 2014. "The warehouse-inventory-transportation problem for supply chains," European Journal of Operational Research, Elsevier, vol. 237(2), pages 690-700.
    5. repec:eee:ejores:v:277:y:2019:i:2:p:561-573 is not listed on IDEAS
    6. Adam N. Elmachtoub & Retsef Levi, 2016. "Supply Chain Management with Online Customer Selection," Operations Research, INFORMS, vol. 64(2), pages 458-473, April.
    7. Hossein Abouee-Mehrizi & Opher Baron & Oded Berman, 2014. "Exact Analysis of Capacitated Two-Echelon Inventory Systems with Priorities," Manufacturing & Service Operations Management, INFORMS, vol. 16(4), pages 561-577, October.
    8. Takahashi, Katsuhiko & Aoi, Takahiko & Hirotani, Daisuke & Morikawa, Katsumi, 2011. "Inventory control in a two-echelon dual-channel supply chain with setup of production and delivery," International Journal of Production Economics, Elsevier, vol. 133(1), pages 403-415, September.
    9. repec:spr:annopr:v:273:y:2019:i:1:d:10.1007_s10479-016-2338-6 is not listed on IDEAS
    10. Gayon, J.-P. & Massonnet, G. & Rapine, C. & Stauffer, G., 2016. "Constant approximation algorithms for the one warehouse multiple retailers problem with backlog or lost-sales," European Journal of Operational Research, Elsevier, vol. 250(1), pages 155-163.
    11. repec:spr:annopr:v:238:y:2016:i:1:d:10.1007_s10479-015-2073-4 is not listed on IDEAS
    12. Oğuz Solyalı & Haldun Süral, 2012. "The one-warehouse multi-retailer problem: reformulation, classification, and computational results," Annals of Operations Research, Springer, vol. 196(1), pages 517-541, July.
    13. Niv Buchbinder & Tracy Kimbrel & Retsef Levi & Konstantin Makarychev & Maxim Sviridenko, 2013. "Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms," Operations Research, INFORMS, vol. 61(4), pages 1014-1029, August.
    14. Retsef Levi & Cong Shi, 2013. "Approximation Algorithms for the Stochastic Lot-Sizing Problem with Order Lead Times," Operations Research, INFORMS, vol. 61(3), pages 593-602, June.

    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:inm:ormnsc:v:54:y:2008:i:4:p:763-776. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Matthew Walls). General contact details of provider: http://edirc.repec.org/data/inforea.html .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.