A simple and fast 2-approximation algorithm for the one warehouse multi-retailer problem
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | STAUFFER, Gautier | |
| hal.structure.identifier | Gestion et Conduite des Systèmes de Production [G-SCOP_GCSP] | |
| dc.contributor.author | MASSONNET, Guillaume | |
| hal.structure.identifier | Informatique et Distribution [ID-IMAG] | |
| dc.contributor.author | RAPINE, Christophe | |
| hal.structure.identifier | Gestion et Conduite des Systèmes de Production [G-SCOP_GCSP] | |
| dc.contributor.author | GAYON, Jean-Philippe | |
| dc.date.accessioned | 2024-04-04T02:28:09Z | |
| dc.date.available | 2024-04-04T02:28:09Z | |
| dc.date.issued | 2011-01-23 | |
| dc.date.conference | 2011-01-23 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/190077 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.publisher | SIAM | |
| dc.title.en | A simple and fast 2-approximation algorithm for the one warehouse multi-retailer problem | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Sciences de l'ingénieur [physics] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2011 | |
| bordeaux.country | US | |
| bordeaux.conference.city | San Francisco | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | inria-00539042 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00539042v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2011-01-23&rft.au=STAUFFER,%20Gautier&MASSONNET,%20Guillaume&RAPINE,%20Christophe&GAYON,%20Jean-Philippe&rft.genre=unknown |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||