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 [2], we obtain a combinatorial algorithm with a performance factor of 3.27 for any k ≥ 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 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 significantly better than 3, which is currently the best approximation ratio for the k-level problem provided by the non-combinatorial algorithm due to Aardal, Chudak, and Shmoys [1].