一般设施定位问题计算复杂度和近似算法研究

摘要

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