Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem

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 ≥ 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 ∞. The values of h(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 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].