Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
复制标题
DOI：
10.1007/3-540-45061-0_13
复制
发表时间：
2003-06
期刊：
影响因子：
--
通讯作者：
A. Ageev;Y. Ye;Jiawei Zhang
中科院分区：
文献类型：
--
作者：
A. Ageev;Y. Ye;Jiawei Zhang
在本文中，我们提出了针对 k 级设施定位问题的改进组合近似算法。首先，通过修改[2]中开发的路径缩减，我们获得了对于anyk≥2性能因子为3.27的组合算法，从而改进了之前的4.56界限。然后我们开发另一种具有更好性能保证的组合算法，并使用第一个算法作为子程序。后一种算法可以递归地实现并实现保证因子h(k)，其中对于anyk，h(k)严格小于3.27并且对于δ趋向于3.27。 h(k) 的值可以很容易地以任意精度计算：h(2) ≈ 2.4211，h(3) ≈ 2.8446，h(4) ≈ 3.0565，h(5) ≈ 3.1678 等等。因此，对于 k= 2 和 k= 3 的情况，第二组合算法确保了显着优于 3 的逼近因子，这是目前 Aardal、Chudak 和 Shmoys [1] 的非组合算法提供的 k 级问题的最佳逼近率。
In this paper we present improved combinatorial approximation algorithms for thek-level facility location problem. First, by modifying the path reduction developed in [2], we obtain a combinatorial algorithm with a performance factor of 3.27 for anyk≥ 2, thus improving the previous bound of 4.56. Then we develop another combinatorial algorithm that has a better performance guarantee and uses the first algorithm as a subroutine. The latter algorithm can be recursively implemented and achieves a guarantee factorh(k), whereh(k) is strictly less than 3.27 for anykand tends to 3.27 askgoes to δ. The values ofh(k) can be easily computed with an arbitrary accuracy:h(2) ≈ 2.4211,h(3) ≈ 2.8446,h(4) ≈ 3.0565,h(5) ≈ 3.1678 and so on. Thus, for the cases ofk= 2 andk= 3 the second combinatorial algorithm ensures an approximation factor significantly better than 3, which is currently the best approximation ratio for thek-level problem provided by the non-combinatorial algorithm due to Aardal, Chudak, and Shmoys [1].