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
- Randomized algorithms
- Facility location
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. https://doi.org/10.1016/j.dam.2009.11.007