English

运筹学学报 >

2018 , Vol. 22 >Issue 3: 49 - 58

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2018.03.005

运筹学

平方度量动态设施选址问题的近似算法

展开
  • 1. 北京工业大学应用数理学院, 北京 100124; 2. 山东建筑大学计算机科学与技术学院, 济南 250101

收稿日期: 2017-11-02

  网络出版日期: 2018-09-15

基金资助

国家自然科学基金(Nos. 11871081, 11801251), 山东省绿色建筑协同创新中心团队建设基金(No. Z0013)

收起

An approximation algorithm for the squared metric dynamic facility location problem

Expand
  • 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

Received date: 2017-11-02

  Online published: 2018-09-15

Fold

摘要

研究了单阶段度量设施选址问题的推广问题平方度量动态设施选址问题. 研究中首先利用原始对偶技巧得到 9-近似算法, 然后利用贪婪增广技巧将近似比改进到2.606, 最后讨论了该问题的相应变形问题.

关键词： 设施选址问题; 近似算法; NP-难

本文引用格式

姜燕君, 徐大川, 张冬梅 . 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018 , 22(3) : 49 -58 . DOI: 10.15960/j.cnki.issn.1007-6093.2018.03.005

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-dual scheme 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.

Key words： facility location problem; approximation algorithm; NP-hard

Options
文章导航

/

〈 〉