| 软容量约束的动态设施选址问题的近似算法 |
| |
| 引用本文： | 姜春艳,李改弟.软容量约束的动态设施选址问题的近似算法[J].系统科学与数学,2012,32(4):476-484. |
| |
| 作者姓名： | 姜春艳 李改弟 |
| |
| 作者单位： | 1. 武警学院基础部,廊坊065000;北京工业大学应用数理学院,北京100124
2. 北京工业大学应用数理学院,北京,100124 |
| |
| 基金项目： | 国家自然科学基金(11071268);北京市教育委员会科技计划面上项目(KM201210005033)资助课题 |
| |
| 摘 要： | 考虑软容量约束的动态设施选址问题.假设设施的开放费用及连接费用都与时间有关,而且每一个设施均有容量约束.对此问题给出了第一个近似比为6的原始对偶(组合)算法.运行贪婪增加程序后,近似比进一步改进到3.7052.
|
| 关 键 词： | 软容量约束动态设施选址问题 对偶 近似算法 |
AN APPROXIMATION ALGORITHM FOR THE SOFT-CAPACITATED DYNAMIC FACILITY LOCATION PROBLEM |
| |
| JIANG Chunyan
,
LI Gaidi.AN APPROXIMATION ALGORITHM FOR THE SOFT-CAPACITATED DYNAMIC FACILITY LOCATION PROBLEM[J].Journal of Systems Science and Mathematical Sciences,2012,32(4):476-484. |
| |
| Authors: | JIANG Chunyan LI Gaidi |
| |
| Institution: | (College of Applied Sciences,Beijing University of Technology,Beijing 100124) |
| |
| Abstract: | The paper considers the soft-capacitated dynamic facility location problem (SCDFLP).It is assumed that the facility open cost and the connection cost are time-dependent, and each facility has a capacity.We present the first primal-dual(combinatorial) approximation algorithm for the problem with approximation ratio 6.We further improve the approximation ration to 3.7052 using greedy augmentation scheme. |
| |
| Keywords: | Soft-capacitated dynamic facility location problem dual approximation algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
