In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems.

Approximation algorithms, Facility location, Randomized algorithms,
Econometric Institute Reprint Series
Discrete Applied Mathematics
Erasmus Research Institute of Management

Gabor, A.F, & van Ommeren, J.C.W. (2010). A new approximation algorithm for the multilevel facility location problem. Discrete Applied Mathematics, 158(5), 453–460. doi:10.1016/j.dam.2009.11.007