Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
Authors:
- Alexander AgeevAAAlexander Ageev
- Yinyu YeYYYinyu Ye
- Jiawei ZhangJZJiawei Zhang
- 1 January 2004
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 18 (1) , 207-217
Abstract
In this paper we present improved combinatorial approximation algorithms for the k-level facility location problem. First, by modifying the path reduction developed in [A. A. Ageev, Oper. Res. Lett., 30 (2002), pp. 327--332], we obtain a combinatorial algorithm with a performance factor of 3.27 for any k \ge 2, thus improving the previous bound of 4.56 achieved by a combinatorial algorithm. 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 factor h(k), where h(k) is strictly less than 3.27 for any k and tends to 3.27 as k goes to $\infty$. The values of h(k) can be easily computed with an arbitrary accuracy: h(2)\approx 2.4211, h(3)\approx 2.8446, h(4)\approx 3.0565, h(5)\approx 3.1678, and so on. Thus, for the cases of k=2 and k=3 the second combinatorial algorithm ensures an approximation factor substantially better than 3, which is currently the best approximation ratio for the k-level problem provided by the noncombinatorial algorithm due to Aardal, Chudak, and Shmoys [Inform. Process. Lett., 72 (1999), pp. 161--167].
Keywords
This publication has 9 references indexed in Scilit:
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LPJournal of the ACM, 2003
- Cost-distance: two metric network design2002
- Improved Approximation Algorithms for Metric Facility Location Problems2002
- Improved approximation algorithms for multilevel facility location problemsOperations Research Letters, 2002
- A new greedy approach for facility location problems2002
- A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem2001
- Approximation Algorithms for Facility Location Problems2000
- A 3-approximation algorithm for the -level uncapacitated facility location problemInformation Processing Letters, 1999
- Greedy Strikes Back: Improved Facility Location AlgorithmsJournal of Algorithms, 1999