Mostrar el registro sencillo del ítem

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

hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorSTAUFFER, Gautier
hal.structure.identifierGestion et Conduite des Systèmes de Production [G-SCOP_GCSP]
dc.contributor.authorMASSONNET, Guillaume
hal.structure.identifierInformatique et Distribution [ID-IMAG]
dc.contributor.authorRAPINE, Christophe
hal.structure.identifierGestion et Conduite des Systèmes de Production [G-SCOP_GCSP]
dc.contributor.authorGAYON, Jean-Philippe
dc.date.accessioned2024-04-04T02:28:09Z
dc.date.available2024-04-04T02:28:09Z
dc.date.issued2011-01-23
dc.date.conference2011-01-23
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190077
dc.description.abstractEnWe 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.isoen
dc.publisherSIAM
dc.title.enA simple and fast 2-approximation algorithm for the one warehouse multi-retailer problem
dc.typeCommunication dans un congrès
dc.subject.halSciences de l'ingénieur [physics]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleProceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2011
bordeaux.countryUS
bordeaux.conference.citySan Francisco
bordeaux.peerReviewedoui
hal.identifierinria-00539042
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00539042v1
bordeaux.COinSctx_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


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem