一类多产品选址算法的若干进展

doi:10.3778/j.issn.1002-8331.2009.17.067

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (17): 221-224.DOI: 10.3778/j.issn.1002-8331.2009.17.067

一类多产品选址算法的若干进展

易斌¹,李荣珩²

1.湖南铁路科技职业技术学院，湖南株洲 412000
2.湖南师范大学数学与计算机学院，长沙 410081

收稿日期:2008-04-09 修回日期:2008-07-08 出版日期:2009-06-11 发布日期:2009-06-11
通讯作者: 易斌

Several progress about approximation algorithm for k-PUFLPN

YI Bin¹,Li Rong-heng²

1.Hunan Railway College of Science & Technology，Zhuzhou，Hunan 412000，China
2.College of Mathematics and Computer Science，Hunan Normal University，Changsha 410081，China

Received:2008-04-09 Revised:2008-07-08 Online:2009-06-11 Published:2009-06-11
Contact: YI Bin

摘要/Abstract

摘要： 在对k-种产品选址问题的前期探讨中，提出了一种用于求解k-PUFLPN（即：设建厂费用为零时，k-种产品工厂选址问题）的近似算法ME，并证明了该算法的最坏性能比不大于3k/2-1，从而把性能比从2k-1提高到3k/2-1。基于前期对算法已有的分析和结论之上，进一步对该算法求解2-种产品选址模型的紧界进行了讨论。通过构造2-种产品模型的实例，给出了2是算法ME求解2-种产品选址问题的紧界这一结论。对2-种产品选址问题的整性间隙也进行了分析和讨论。

关键词: 近似算法, 工厂选址, k-种产品, 紧界, 整性间隙

Abstract: In the preliminary discussion of the k-product facility location problem，a 3k/2-1 approximation algorithm Me is given for the problem which assumed that fixed setup cost are zero．Based on the preliminary analysis and conclusions，the tight bound of the improved algorithm Me is discussed for 2-PUFLPN．By constructing example of 2-PUFLPN，A conclusion is given that 2 is a tight bound for improved algorithm ME.At the same time，the integrality gap of 2-PUFLPN is analyzed.

Key words: approximation algorithm, facility location, k-product, tight bound, integrality gap

易斌¹,李荣珩². 一类多产品选址算法的若干进展[J]. 计算机工程与应用, 2009, 45(17): 221-224.

YI Bin¹,Li Rong-heng². Several progress about approximation algorithm for k-PUFLPN[J]. Computer Engineering and Applications, 2009, 45(17): 221-224.

[1]	曾维新1，赵翔1，2，冯滔1，唐九阳1，2. 面向领域的命名实体消歧方法改进研究[J]. 计算机工程与应用, 2018, 54(17): 126-134.
[2]	蒋小娟1，张安1，陈永1，陈光亭2. 内部节点受限的最小生成树问题算法研究[J]. 计算机工程与应用, 2017, 53(10): 35-37.
[3]	聂文艳1，王仲根2. 应用ACA算法快速分析导体目标电磁散射特性[J]. 计算机工程与应用, 2015, 51(4): 232-234.
[4]	王继强. 集合覆盖问题的模型与算法[J]. 计算机工程与应用, 2013, 49(17): 15-17.
[5]	纪鹏宇1，谢红1，赵蕴龙2. 一种中继节点上的网络-信道编码联合设计方案[J]. 计算机工程与应用, 2012, 48(34): 102-106.
[6]	王继强. 基于TSP的图的路包装问题的算法研究[J]. 计算机工程与应用, 2011, 47(21): 220-222.
[7]	何晓琼，陈冲，李荣珩. 工厂地址集中的k-种产品选址问题的近似算法[J]. 计算机工程与应用, 2010, 46(8): 238-241.
[8]	高文宇. 有向图连通支配集求解算法[J]. 计算机工程与应用, 2010, 46(21): 9-13.
[9]	黄金贵. 具有优先链约束的网格作业多资源调度问题[J]. 计算机工程与应用, 2009, 45(6): 48-51.
[10]	黄金贵. 应用团划分方法改进多处理机任务近似调度[J]. 计算机工程与应用, 2009, 45(4): 4-8.
[11]	许金星，吴素萍. 旅行售货员问题的图论近似算法[J]. 计算机工程与应用, 2009, 45(32): 51-52.
[12]	沈庆涛,张振宇. 高效的求解TSP问题的近似算法[J]. 计算机工程与应用, 2008, 44(35): 46-49.
[13]	黄金贵. 任意处理时间的多处理机任务调度近似算法[J]. 计算机工程与应用, 2008, 44(33): 7-9.
[14]	黄金贵. 单位处理时间的多处理机任务调度近似算法[J]. 计算机工程与应用, 2008, 44(32): 26-28.
[15]	李勇,蒋建国,夏娜. 一种求解单任务Agent联盟生成的近似算法[J]. 计算机工程与应用, 2008, 44(2): 29-31.

一类多产品选址算法的若干进展

Several progress about approximation algorithm for k-PUFLPN

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics