摘要
本文提出了一种针对可分解子次模订单成本函数的子模联合补货问题（SJRP）的近似算法。在SJRP中，中心规划者协调对多个物品的订单，以满足有限离散规划周期内的确定性需求，同时最小化总的持有和订单成本，其中后者建模为所订购物品子集的子模函数。
考虑的订单成本函数基于将物品划分为 $k$ 类的分解，其中成本是各类别内加权总量的函数，并允许通过联合成本函数在类别之间进行任意交互。所提出的算法通过一种新颖的水填充过程，将线性规划松弛的解决方案进行分区，将分数解决方案按边际成本划分为嵌套区域，然后从每个区域中选择一个订单，以获得可行的整数计划。最终算法实现了 $O(k)$ 的近似。当类别数量 $k$ 固定时，这为这一广泛的子模订单成本类提供了第一个常数因子保证，显著扩展了已知此类保证的成本函数范围。
博主点评： 本文提出的近似算法不仅在理论上具有重要意义，还在实际应用中有助于优化库存管理，尤其是在多品类商品的复杂场景中。通过水填充过程的创新，算法的有效性得到了显著提升，值得关注和深入研究。