摘要
在对k-种产品选址问题的前期探讨中,提出了一种用于求解k-PUFLPN(即:设建厂费用为零时,k-种产品工厂选址问题)的近似算法ME,并证明了该算法的最坏性能比不大于3k/2-1,从而把性能比从2k-1提高到3k/2-1。基于前期对算法已有的分析和结论之上,进一步对该算法求解2-种产品选址模型的紧界进行了讨论。通过构造2-种产品模型的实例,给出了2是算法ME求解2-种产品选址问题的紧界这一结论。对2-种产品选址问题的整性间隙也进行了分析和讨论。
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.
出处
《计算机工程与应用》
CSCD
北大核心
2009年第17期221-224,共4页
Computer Engineering and Applications
基金
国家自然科学基金(No.10771060)~~
关键词
近似算法
工厂选址
k-种产品
紧界
整性间隙
approximation algorithm
facility location
k-product
tight bound
integrality gap
