Approximation algorithms for the dynamic k-level facility location problems
Approximation algorithms for the dynamic k-level facility location problems
复制标题
动态k级设施选址问题的近似算法
DOI：
10.1016/j.tcs.2020.05.022
复制
发表时间：
2020-05
影响因子：
1.1
通讯作者：
Xiaoyan Zhang
中科院分区：
文献类型：
--
作者：
Limin Wang;Zhao Zhang;Chenchen Wu;Dachuan Xu;Xiaoyan Zhang
In this paper, we first consider a dynamick-level facility location problem, which is a generalization of thek-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 dynamick-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.
登录
查看更多内容
DOI：
10.1016/j.orl.2005.06.002
发表时间：
2006-07
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
Dachuan Xu;D. Du
通讯作者：
Dachuan Xu;D. Du
DOI：
10.1016/s0020-0190(99)00144-1
发表时间：
1999-12
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
K. Aardal;Fabián A. Chudak;D. Shmoys
通讯作者：
K. Aardal;Fabián A. Chudak;D. Shmoys
DOI：
10.1007/978-3-642-31594-7_14
发表时间：
2012-07
期刊：
--
影响因子：
--
作者：
J. Byrka;Bartosz Rybicki
通讯作者：
J. Byrka;Bartosz Rybicki
DOI：
10.1007/3-540-45061-0_13
发表时间：
2003-06
期刊：
--
影响因子：
--
作者：
A. Ageev;Y. Ye;Jiawei Zhang
通讯作者：
A. Ageev;Y. Ye;Jiawei Zhang
DOI：
10.1007/s10255-014-0277-z
发表时间：
2014-03
期刊：
Acta Mathematicae Applicatae Sinica, English Series
影响因子：
--
作者：
Chun-yan Jiang;Gaidi Li;Zhen Wang
通讯作者：
Chun-yan Jiang;Gaidi Li;Zhen Wang