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.

Additional Metadata
Keywords Approximation algorithms, Facility location, Randomized algorithms
Persistent URL dx.doi.org/10.1016/j.dam.2009.11.007, hdl.handle.net/1765/18217
Citation
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