Paper Info
Title
A new approximation algorithm for the multilevel facility location problem
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.
Year
DOI
Venue
2010
10.1016/j.dam.2009.11.007
Discrete Applied Mathematics
Keywords
Field
DocType
facility location,approximation algorithms,approximation algorithm,linear program,randomized algorithms,new approximation algorithm,polynomial number,multilevel facility location problem,new integer programming formulation,novel 3-approximation algorithm,randomized algorithm,facility location problem
Randomized algorithm,Approximation algorithm,Mathematical optimization,Polynomial,Computer science,Theoretical computer science,Facility location problem,Integer programming,Linear programming,1-center problem
Journal
Volume
Issue
ISSN
158
5
Discrete Applied Mathematics
Citations 
PageRank 
References 
22
0.83
21
Authors
2
Name
Order
Citations
PageRank
Adriana F. Gabor1484.56
Jan-kees C. W. Van Ommeren2738.53