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. [ABSTRACT FROM AUTHOR]