EconPapers    
Economics at your fingertips  
 

A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem

Retsef Levi (), Robin Roundy (), David Shmoys () and Maxim Sviridenko ()
Additional contact information
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

Management Science, 2008, vol. 54, issue 4, 763-776

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.

Keywords: deterministic inventory theory; approximation algorithms; linear programming (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (25)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.1070.0781 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:54:y:2008:i:4:p:763-776

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().

 
Page updated 2025-03-19
Handle: RePEc:inm:ormnsc:v:54:y:2008:i:4:p:763-776