Approximation algorithms for the dynamic k-level facility location problems

In this paper, we first consider a dynamic k-level facility location problem, which is a generalization of the k-level facility location problem when considering time factor. We present a combinatorial primal-dual approximation algorithm for this problem which finds a constant factor approximate solution. Then, we investigative the dynamic k-level facility location problem with submodular penalties and outliers, which extend the existing problem on two fronts, namely from static to dynamic and from without penalties (outliers) to penalties (outliers) allowed. Based on primal-dual technique and the triangle inequality property, we also give two constant factor approximation algorithms for the dynamic problem with submodular penalties and outliers, respectively.

Authors

• Limin Wang State Key Laboratory for Novel Software Technology, Nanjing University, China
• Zhao Zhang Hefei University of Technology, Yunnan Key Laboratory of Software Engineering
• Chenchen Wu
• Dachuan Xu Beijing University of Technology, Beijing, China
• Xiaoyan Zhang

Keywords

• Approximation algorithm
• Primal-dual
• Dynamic
• Facility location
• Submodular penalties
• Outliers