Approximation Procedures for the One-Warehouse Multi-Retailer System
针对单仓库多零售商系统，提出两种启发式方法：第一种在指定评估点数下相对误差逼近2.014%，复杂度O(n)；第二种针对固定区间策略，给出全多项式时间近似方案，误差可调且计算量随1/√ε线性增长。
Two heuristic procedures for a one-warehouse multi-retailer system are developed. Based on the accuracy desired, the first heuristic evaluates a specified number of points. The relative error is within a bound that approaches 1/(√2 ln 2) − 1 ≈ 2.014%. The complexity of the heuristic is O(n) for a fixed number of evaluations. Although our bound only approaches the one of Roundy (1985), when only a small number of points are evaluated, our method is faster. We show that the bound for our procedure and two bounds proposed by Roundy (1985) are tight. The second heuristic pertains to a class of polities called stationary interval policies. For this class of policies, we develop a fully polynomial-time approximation scheme where the relative error is within ε > 0, and the computational effort increases as a linear function of 1/√ε. Computational experiments show that these heuristics perform well in practice.