@inproceedings{eb04ecb77d9b46a992e136d1c843c2c5,

title = "Approximation algorithms and hardness results for the joint replenishment Problepm with constant demands",

abstract = "In the Joint Replenishment Problem (JRP), the goal is to coordinate the replenishments of a collection of goods over time so that continuous demands are satisfied with minimum overall ordering and holding costs. We consider the case when demand rates are constant. Our main contribution is the first hardness result for any variant of JRP with constant demands. When replenishments per commodity are required to be periodic and the time horizon is infinite (which corresponds to the so-called general integer model with correction factor), we show that finding an optimal replenishment policy is at least as hard as integer factorization. This result provides the first theoretical evidence that the JRP with constant demands may have no polynomial-time algorithm and that relaxations and heuristics are called for. We then show that a simple modification of an algorithm by Wildeman et al. (1997) for the JRP gives a fully polynomial-time approximation scheme for the general integer model (without correction factor). We also extend their algorithm to the finite horizon case, achieving an approximation guarantee asymptotically equal to √9/8.",

keywords = "Continuous demand, Correction factors, Demand rates, Finite horizons, Fully polynomial time approximation schemes, Hardness result, Holding costs, Integer factorization, Joint replenishment, Joint replenishment problem, Polynomial-time algorithms, Replenishment policy, Simple modifications, Time horizons",

author = "Schulz, {Andreas S.} and Claudio Telha",

note = "{\textcopyright} 2011 Springer-Verlag Berlin Heidelberg.; null ; Conference date: 05-09-2011 Through 09-09-2011",

year = "2011",

doi = "10.1007/978-3-642-23719-5_53",

language = "English",

isbn = "9783642237188",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "628--639",

booktitle = "Algorithms, ESA 2011 - 19th Annual European Symposium, Proceedings",

}