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 Bin1,Li Rong-heng2   

  1. 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,李荣珩2   

  1. 1.湖南铁路科技职业技术学院,湖南 株洲 412000
    2.湖南师范大学 数学与计算机学院,长沙 410081
  • 通讯作者: 易 斌

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-种产品, 紧界, 整性间隙