Near-Optimal Dynamic Policies for Joint Replenishment in Continuous/Discrete Time

The principal contribution of this paper consists in developing a wide range of algorithmic ideas and analytical insights around the continuous-time joint replenishment problem, culminating in a deterministic framework for efficiently approximating optimal dynamic policies to any desired level of accuracy. These advances enable us to derive a compactly encoded replenishment policy whose long-run average cost is within factor $1+ϵ$ of the dynamic optimum, arriving at an efficient polynomial-time approximation scheme (EPTAS). Technically speaking, our approach hinges on affirmative resolutions to two fundamental open questions. In relation to feasibility of scalable discretization, we devise the first efficient discretization-based framework for approximating the joint replenishment problem. Specifically, we prove that every continuous-time infinite-horizon instance can be reduced to a corresponding discrete-time $O(\frac{n^3}{{ϵ}^6})$-period instance, while incurring a multiplicative optimality loss of at most $1+ϵ$. Then, in regard to enhanced guarantees for the discrete setting, we improve on the $O(2^{2^{O(1/ϵ)}}·{(nT)}^{O(1)})$-time approximation scheme of Nonner and Sviridenko (IPCO ’13) for the discrete-time joint replenishment problem. Beyond an exponential improvement in running time, we demonstrate that the key pillars of their methodology—randomization and hierarchical decompositions—can be entirely avoided, while concurrently offering a streamlined analysis.

Funding: This work was supported by the Israel Science Foundation [Grant 1407/20].