| 平方度量动态设施选址问题的近似算法 |
| |
| 引用本文： | 姜燕君,徐大川,张冬梅.平方度量动态设施选址问题的近似算法[J].运筹学学报,2018,22(3):49-58. |
| |
| 作者姓名： | 姜燕君 徐大川 张冬梅 |
| |
| 作者单位： | 1. 北京工业大学应用数理学院, 北京 100124;
2. 山东建筑大学计算机科学与技术学院, 济南 250101 |
| |
| 基金项目： | 国家自然科学基金(Nos. 11871081, 11801251), 山东省绿色建筑协同创新中心团队建设基金(No. Z0013) |
| |
| 摘 要： | 研究了单阶段度量设施选址问题的推广问题平方度量动态设施选址问题. 研究中首先利用原始对偶技巧得到 9-近似算法, 然后利用贪婪增广技巧将近似比改进到2.606, 最后讨论了该问题的相应变形问题.
|
| 关 键 词： | 设施选址问题 近似算法 NP-难 |
| 收稿时间： | 2017-11-02 |
An approximation algorithm for the squared metric dynamic facility location problem |
| |
| JIANG Yanjun,XU Dachuan,ZHANG Dongmei.An approximation algorithm for the squared metric dynamic facility location problem[J].OR Transactions,2018,22(3):49-58. |
| |
| Authors: | JIANG Yanjun XU Dachuan ZHANG Dongmei |
| |
| Institution: | 1. College of Applied Sciences, Beijing University of Technology, Beijing 100124, China;
2. School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, China |
| |
| Abstract: | We consider a generalization of the classic single-period metric facility location problem, which is the squared metric dynamic facility location problem. We utilize the primal-dualscheme to design a 9-approximation algorithm. Then the approximation ratio is improved to 2.606 by the greedy improvement technique. We also give some discussion for several variants of the squared metric dynamic facility location problem in future work. |
| |
| Keywords: | facility location problem approximation algorithm NP-hard |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
