|
|||||
|
|
A new approximation algorithm for the multilevel facility location problem |
|
| Authors: | Adriana F Gabor Jan-Kees CW van Ommeren |
| Institution: | a Econometric Institute, Erasmus University Rotterdam, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands b Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands |
| 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. |
| Keywords: | Facility location Approximation algorithms Randomized algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ | |