This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Levi, R. Articles by Sviridenko, M. Search for Related Content

A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem

Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
School of Operations Research and Information Engineering and Department of Computer Science, Cornell University, Ithaca, New York 14853
IBM T. J. Watson Research Center, Yorktown Heights, New York 10598
retsef{at}mit.edu
robin{at}orie.cornell.edu
shmoys{at}cs.cornell.edu
sviri{at}us.ibm.com

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.

Key Words: deterministic inventory theory; approximation algorithms; linear programming
History: Received: July 14, 2004;