In this paper, we study the dynamic facility location problem with submodular penalties (DFLPSP). We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.
基金Supported in part by Hebei Province Department of Education Fund under Grant No.Z2012017the National Natural Science Foundation of China under Grant No.11371001 and 11201013
文摘In this paper, we study the dynamic facility location problem with submodular penalties (DFLPSP). We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.