A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem

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.

• 저널Management Science · 54(4) · 763–776
• 토픽Optimization and Search Problems · Computer Networks and Communications
• DOI10.1287/mnsc.1070.0781
• 저자Retsef Levi, R. Roundy, David B. Shmoys, Maxim Sviridenko