Better Approximation Bounds for the Joint Replenishment Problem
Better Approximation Bounds for the Joint Replenishment Problem
复制标题
联合补给问题的更好的近似界限
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
J. Sgall
中科院分区：
文献类型：
--
作者：
Marcin Bienkowski;J. Byrka;M. Chrobak;Lukasz Jez;Dorian Nogneng;J. Sgall
联合补给问题（JRP）通过共享的仓库处理从供应商到零售商的优化货物。仓库向订购它们的零售商，将货物运送到零售商ρ的零售商还有固定的成本Cρ。时间的非降低功能，每个订单都不同。
JRP在操作研究中进行了很好的研究，最近在近似算法的领域中，最适合的等待成本功能。在等待的情况下，但订单的截止日期为硬度。在在线方案中，这两个结果都可以。等待成本功能是线性的。
我们为JRP提供了几个新的近似结果，我们给出了1.791的算法，打破了1.8的障碍。 1.09在在线案例中，我们在JRP-L的竞争比率上显示了2.754（以及JRP）为了我们证明最佳竞争比为2。
The Joint Replenishment Problem (JRP) deals with optimizing shipments of goods from a supplier to retailers through a shared warehouse. Each shipment involves transporting goods from the supplier to the warehouse, at a fixed cost C, followed by a redistribution of these goods from the warehouse to the retailers that ordered them, where transporting goods to a retailer ρ has a fixed cost cρ. In addition, we incur waiting costs for each order, possibly an arbitrary non-decreasing function of time, different for each order. The objective is to minimize the overall cost of satisfying all orders, namely the sum of all shipping and waiting costs.
JRP has been well studied in Operations Research and, more recently, in the area of approximation algorithms. For arbitrary waiting cost functions, the best known approximation ratio is 1.8. This ratio can be reduced to a 1.574 for the JRP-D model, where there is no cost for waiting but orders have deadlines. As for hardness results, it is known that the problem is APX-hard and that the natural linear program for JRP has integrality gap at least 1.245. Both results hold even for JRP-D. In the online scenario, the best lower and upper bounds on the competitive ratio are 2.64 and 3, respectively. The lower bound of 2.64 applies even to the restricted version of JRP, denoted JRP-L, where the waiting cost function is linear.
We provide several new approximation results for JRP. In the offline case, we give an algorithm with ratio a 1.791, breaking the barrier of 1.8. We also show that the integrality gap of the linear program for JRP-L is at least 12/11 a 1.09. In the online case, we show a lower bound of a 2.754 on the competitive ratio for JRP-L (and thus JRP as well), improving the previous bound of 2.64. We also study the online version of JRP-D, for which we prove that the optimal competitive ratio is 2.
影响因子：
2
作者：
Bienkowski M
通讯作者：
Bienkowski M