The main contribution of this paper resides in developing a new algorithmic approach for addressing the continuous-time joint replenishment problem, termed $\Psi$-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-80's. Moreover, in light of recent intractability results, by proposing an efficient polynomial-time approximation scheme (EPTAS) for the joint replenishment problem, we resolve the long-standing open question regarding the computational complexity of this classical setting.
翻译:本文的主要贡献在于制定新的算法方法来解决连续时间联合充资问题,称为“美元-美元-双向匹配”,后一种机制,即我们通过这一机制使多种经济秩序数量模型同步,使我们能够设计出一种纯粹的计算法,以便在任何准确程度内有效地接近最佳政策,因此,我们的工作是对自80年代中期以来这方面最先进的2美元政策在数量上的首次改进。 此外,鉴于近期的可吸引性结果,通过为联合充资问题提出一项高效的多时近似计划,我们解决了这一传统环境的计算复杂性的长期未决问题。