An Approximate Dynamic-Programming Approach to the Joint Replenishment Problem

Abstract

The main contribution of this paper is to propose a new dynamic-programming approach that ε-approximates the joint replenishment problem, with stationary demands and holding costs, in its discrete-time finite-horizon setting. Our first and foremost objective is to show that the computation time of classical dynamic-programming algorithms can be improved on by orders of magnitude when one is willing to lose an ε-factor in optimality. Based on synthesizing ideas such as commodity aggregation, approximate dynamic programming, and a few guessing tricks, we show that one can attain any required degree of accuracy in near-polynomial time.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 13 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.