Several progress about approximation algorithm for k-PUFLPN

doi:10.3778/j.issn.1002-8331.2009.17.067

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (17): 221-224.DOI: 10.3778/j.issn.1002-8331.2009.17.067

• 工程与应用 • Previous Articles Next Articles

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

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

易斌¹,李荣珩²

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

通讯作者: 易斌

Abstract

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

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

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

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

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

[1]	GOU Haiwen, NING Aibing, HU Qin, ZHANG Huizhen. Reduction Backtracking Algorithm for Uncapacitated Facility Location Problem With Penalties [J]. Computer Engineering and Applications, 2020, 56(24): 43-49.
[2]	WANG Haoxiang, LI Na, LI Qiangyi. Research on Improved Virtual Force Maximum Coverage Location Algorithm [J]. Computer Engineering and Applications, 2020, 56(20): 220-225.
[3]	CHEN Gang, FU Jiangyue. Drone Distribution Center Location Problem Under Military-Civilian Integration Strategy [J]. Computer Engineering and Applications, 2019, 55(8): 226-231.
[4]	HE Yongmei, NING Aibing, PENG Dajiang, SHANG Chunjian, ZHANG Huizhen. Competitive Decision Algorithm for Soft-Capacitated Facility Location Problem [J]. Computer Engineering and Applications, 2019, 55(3): 50-54.
[5]	LIU Chunmiao, ZHANG Huizhen. Hybrid bat algorithm for un-capacitated facility location problem [J]. Computer Engineering and Applications, 2018, 54(22): 28-34.
[6]	ZENG Weixin1, ZHAO Xiang1，2, FENG Tao1, TANG Jiuyang1，2. Improved domain-oriented named entity disambiguation method study [J]. Computer Engineering and Applications, 2018, 54(17): 126-134.
[7]	JIANG Xiaojuan1, ZHANG An1, CHEN Yong1, CHEN Guangting2. Algorithm for minimum internal nodes constrained spanning tree problem [J]. Computer Engineering and Applications, 2017, 53(10): 35-37.
[8]	LIU Chengkun1, JIA Tao1, GAO Qili1, WANG Yulong1, QIN Kun1, TAO Hongbing2. Study on location and allocation of healthcare center based on improved genetic algorithm [J]. Computer Engineering and Applications, 2016, 52(6): 13-18.
[9]	XIE Wenlong, WEI Guoqiang. Location models for military logistics distribution centers based on scenario analysis [J]. Computer Engineering and Applications, 2015, 51(8): 255-259.
[10]	XIAO Junhua1，2, HOU Yunxian1. Research on emergency facility location model and algorithms for large-scale emergencies [J]. Computer Engineering and Applications, 2013, 49(8): 67-71.
[11]	YU Fuping1，2, SHEN Di1. Improved smoothed [l0] approximation algorithm based on Quasi-Newton direction [J]. Computer Engineering and Applications, 2013, 49(22): 215-218.
[12]	WANG Jiqiang. Model and algorithm for set cover problem [J]. Computer Engineering and Applications, 2013, 49(17): 15-17.
[13]	WANG Jiqiang. Research of algorithm for path packing problem in graphs based on TSP [J]. Computer Engineering and Applications, 2011, 47(21): 220-222.
[14]	HE Xiao-qiong，CHEN Chong，LI Rong-heng. Approximation algorithms for k-product centralized facility location problem [J]. Computer Engineering and Applications, 2010, 46(8): 238-241.
[15]	XIAO Jin-jie，XIE Qing-song，NIU Cui-xia. Test of local search algorithms for uncapacitated facility location problems [J]. Computer Engineering and Applications, 2010, 46(2): 34-36.

Several progress about approximation algorithm for k-PUFLPN

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics