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
dx.doi.org/10.1016/j.dam.2009.11.007, hdl.handle.net/1765/18217
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