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 [Formula: see text] 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 [Formula: see text]-period instance, while incurring a multiplicative optimality loss of at most [Formula: see text]. Then, in regard to enhanced guarantees for the discrete setting, we improve on the [Formula: see text]-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].