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 - GCSP
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 metadatas

https://hal.inria.fr/inria-00539042
Contributor : Gautier Stauffer <>
Submitted on : Tuesday, November 23, 2010 - 5:37:11 PM
Last modification on : Thursday, May 23, 2019 - 11:06:04 AM

Identifiers

  • HAL Id : inria-00539042, version 1

Citation

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⟩

Share

Metrics

Record views

421