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

doi:10.15960/j.cnki.issn.1007-6093.2018.03.005

运筹学学报

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

姜燕君¹徐大川¹ 张冬梅^2,*

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

收稿日期:2017-11-02 出版日期:2018-09-15 发布日期:2018-09-15
通讯作者: 张冬梅 E-mail: zhangdongmei@sdjzu.edu.cn
基金资助:
国家自然科学基金(Nos. 11871081, 11801251), 山东省绿色建筑协同创新中心团队建设基金(No. Z0013)

An approximation algorithm for the squared metric dynamic facility location problem

JIANG Yanjun¹XU Dachuan¹ZHANG Dongmei^2,*

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:2017-11-02 Online:2018-09-15 Published:2018-09-15

摘要/Abstract

摘要：

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

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

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

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

JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2018.03.005.

[1]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[2]	陈如冰, 原晋江. 工件具有加工位置上限最小化加权总误工量的单机排序问题[J]. 运筹学学报, 2020, 24(2): 131-144.
[3]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[4]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[5]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[6]	杨沐明, 黄亚魁, 戴彧虹. 一类多商品设施选址问题的基于线性松弛解的启发式方法[J]. 运筹学学报, 2019, 23(3): 15-26.
[7]	余善恩, 徐文洋, 刘光宇. 圆形区域分散布局问题研究[J]. 运筹学学报, 2018, 22(3): 132-138.
[8]	王一水, 徐大川, 吴晨晨. 关联聚类问题的半定规划舍入算法[J]. 运筹学学报, 2018, 22(1): 67-76.
[9]	苗翠霞, 孟凡晓. 基于退化效应的两台机器流水作业可拒绝排序[J]. 运筹学学报, 2017, 21(2): 66-72.
[10]	徐大川, 许宜诚, 张冬梅. k-平均问题及其变形的算法综述[J]. 运筹学学报, 2017, 21(2): 101-109.
[11]	陈光亭, 陈蕾, 张安, 陈永. 可转包两台流水作业机排序的近似算法[J]. 运筹学学报, 2016, 20(4): 109-114.
[12]	仲维亚, 马晓茹. 带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报, 2016, 20(4): 93-101.
[13]	孙婷, 李改弟, 徐文青. 最大割问题和最大平分割问题基于半定规划松弛的近似算法[J]. 运筹学学报, 2016, 20(3): 21-32.
[14]	方芮, 罗文昌. 带惩罚的容错设施布局问题的近似算法[J]. 运筹学学报, 2016, 20(2): 69-78.
[15]	闫林成, 肖汉, 赵红娟, 孙小淇. 关于可靠性设施布局问题的近似算法[J]. 运筹学学报, 2015, 19(4): 14-24.

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

An approximation algorithm for the squared metric dynamic facility location problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价