A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem
Retsef Levi, Robin Roundy, David Shmoys, Maxim Sviridenko
Management Science · 2008 · Volume 54 · Issue 4
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
Enable JavaScript for citation tools and additional paper interactions.