Skip to Main content Skip to Navigation
New interface
Conference papers

A simple and fast 2-approximation algorithm for the one warehouse multi-retailer problem

Gautier Stauffer 1, 2 Guillaume Massonnet 3 Christophe Rapine 4 Jean-Philippe Gayon 3 
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
3 G-SCOP_GCSP - Gestion et Conduite des Systèmes de Production
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
Abstract : We consider a well-known NP-hard deterministic inventory control problem: the One-Warehouse Multi-Retailer (OWMR) problem. We present a simple combinatorial algorithm to recombine the optimal solutions of the natural single-echelon inventory subproblems into a feasible solution of the OWMR problem. This approach yields a 3approximation. We then show how this algorithm can be improved to a 2-approximation by halving the demands at the warehouse and at the retailers in the subproblems. Both algorithms are purely combinatorial and can be implemented to run in linear time for traditional linear holding costs and quadratic time for more general holding cost structures. We finally show that our technique can be extended to the Joint Replenishment Problem (JRP) with backorders and to the OWMR problem with non-linear holding costs.
Document type :
Conference papers
Complete list of metadata
Contributor : Gautier Stauffer Connect in order to contact the contributor
Submitted on : Tuesday, November 23, 2010 - 5:37:11 PM
Last modification on : Saturday, June 25, 2022 - 7:44:21 PM


  • HAL Id : inria-00539042, version 1


Gautier Stauffer, Guillaume Massonnet, Christophe Rapine, Jean-Philippe Gayon. A simple and fast 2-approximation algorithm for the one warehouse multi-retailer problem. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2011, Jan 2011, San Francisco, United States. ⟨inria-00539042⟩



Record views