论文部分内容阅读
设施定位问题即UFL问题是NP—hard的组合优化问题，是聚类问题领域的热点问题之一，在数据挖掘和分类识别方面有着重要应用．多年来其近似算法研究一直是计算机科学工作者关注的焦点，然而现有研究结果大多关于Metric空间，一般距离空间中该问题结果始终未见．针对最大连接费用至多是最小连接费用ω〉1倍的一般距离空间中设施定位问题，简称一般设施定位问题，借助集合覆盖问题，利用问题归约方法证明其不存在近似性能比小于1．243＋0．316ln（ω-1）的多项式时间近似算法，除非NP真包含DTIME（n^O（log l