Approximation algorithms and hardness results for the joint replenishment Problepm with constant demands

Andreas S. Schulz*, Claudio Telha

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations


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.

Original languageEnglish
Title of host publicationAlgorithms, ESA 2011 - 19th Annual European Symposium, Proceedings
Number of pages12
StatePublished - 2011
Event19th Annual European Symposium on Algorithms, ESA 2011 - Saarbrucken, Germany
Duration: 5 Sep 20119 Sep 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6942 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference19th Annual European Symposium on Algorithms, ESA 2011

Bibliographical note

© 2011 Springer-Verlag Berlin Heidelberg.


  • 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


Dive into the research topics of 'Approximation algorithms and hardness results for the joint replenishment Problepm with constant demands'. Together they form a unique fingerprint.

Cite this