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 greater than or equal to 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 infinity. The values of h( k) can be easily computed with an arbitrary accuracy: h( 2) approximate to 2.4211, h( 3) approximate to 2.8446, h(4) approximate to 3.0565, h(5) approximate to 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].