A constant approximation algorithm for the one-warehouse multiretailer problem

• 成果类型: Article
• 署名作者: Levi, Retsef; Roundy, Robin; Shmoys, David; Sviridenko, Maxim
• 署名单位: Massachusetts Institute of Technology (MIT); Cornell University; Cornell University; International Business Machines (IBM); IBM USA
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.1070.0781
• 发表日期: 2008
• 页码: 763-776
• 关键词: deterministic inventory theory; Approximation algorithms; linear programming

摘要

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.