A new approximation algorithm for the multilevel facility location problem
2010-03-06
Article
volume 158, issue 5 pp 453-460.
This publication is part of collection
| Related Files |
|---|
|
Redirect to Publisher's version
(Publisher's version.url.txt, 43 bytes) |
Repository contains one additional file which is not publicly available
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.
Keywords
