The Continuous-Time Joint Replenishment Problem: ϵ-Optimal Policies via Pairwise Alignment
提出一种新的成对对齐算法，用于连续时间联合补货问题，能高效逼近任意精度的最优策略，首次在定量上优于自1980年代以来的主流2的幂次策略，并解决了该问题的计算复杂性难题。
The main contribution of this paper resides in developing a new algorithmic approach for addressing the continuous-time joint replenishment problem, termed [Formula: see text]-pairwise alignment. The latter mechanism, through which we synchronize multiple economic order quantity models, allows us to devise a purely combinatorial algorithm for efficiently approximating optimal policies within any degree of accuracy. As a result, our work constitutes the first quantitative improvement over power-of-2 policies, which have been state-of-the-art in this context since the mid-1980s. Moreover, in light of recent intractability results, by proposing an efficient polynomial-time approximation scheme for the joint replenishment problem, we resolve the long-standing open question regarding the computational complexity of this classical setting. This paper was accepted by Chung Piaw Teo, optimization. Funding: This work was supported by the Israel Science Foundation [Grant 1407/20].