【摘要】 设施定位问题即UFL问题是NP-hard的组合优化问题,是聚类问题领域的热点问题之一,在数据挖掘和分类识别方面有着重要应用.多年来其近似算法研究一直是计算机科学工作者关注的焦点,然而现有研究结果大多关于Metric空间,一般距离空间中该问题结果始终未见.针对最大连接费用至多是最小连接费用ω>1倍的一般距离空间中设施定位问题,简称一般设施定位问题,借助集合覆盖问题,利用问题归约方法证明其不存在近似性能比小于1.243+0.316ln(ω-1)的多项式时间近似算法,除非NPDTIME(nO(loglogn));设计了一般设施定位问题的局部搜索算法,证明算法近似性能比是(1+ω)/α,ω>1,1≤α≤2.仿真实验表明,一般设施定位问题局部搜索算法的求解质量极高;通过实验进一步研究了该算法并给出了改进方法.更多还原

【Abstract】 Facility location problem, i.e. UFL problem, is an NP-hard combinatorial optimization problem, and one of the hot topics in clustering problem. It has important application in data mining and classification and ranking. Research on approximation algorithms for the problem has been a focus of computer scientists for many years. However, most of the existing results are based on the metric space. The results for the problem in general distance space have not been found all the time. For the facility location problem in general distance space where the maximum connection cost is at most ω>1 times the minimum connection cost, by making use of set cover problem and the method of problem reduction, it is first proved that there are no polynomial time approximation algorithms with approximation ratios smaller than 1.243+0.316ln(ω-1), unless NPDTIME(nO(log log n)), and then a (1+ω)?α local search approximation algorithm for the general facility location problem is proposed, where ω>1, 1≤α≤2. Finally, experimental results show that the quality of solutions obtained by the local search algorithm is remarkable. Through elaborate experiment, the local search algorithm is explored further and the improved method for it is proposed.更多还原