Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 453-460 |
Number of pages | 8 |
Journal | Discrete applied mathematics |
Volume | 158 |
Issue number | 5 |
DOIs | |
Publication status | Published - 6 Mar 2010 |
Keywords
- MSC-68W25
- Approximation algorithms
- Randomized algorithms
- Facility location