| 一般设施定位问题计算复杂度和近似算法研究 |
| |
| 引用本文： | 潘锐,朱大铭,马绍汉. 一般设施定位问题计算复杂度和近似算法研究[J]. 计算机研究与发展, 2007, 44(5): 790-797 |
| |
| 作者姓名： | 潘锐 朱大铭 马绍汉 |
| |
| 作者单位： | 山东大学计算机科学与技术学院,济南,250061;山东大学计算机科学与技术学院,济南,250061;山东大学计算机科学与技术学院,济南,250061 |
| |
| 基金项目： | 国家自然科学基金 , 国家重点基础研究发展计划(973计划) , 山东省自然科学基金 |
| |
| 摘 要： | 设施定位问题即UFL问题是NP-hard的组合优化问题,是聚类问题领域的热点问题之一,在数据挖掘和分类识别方面有着重要应用.多年来其近似算法研究一直是计算机科学工作者关注的焦点,然而现有研究结果大多关于Metric空间,一般距离空间中该问题结果始终未见.针对最大连接费用至多是最小连接费用ω＞1倍的一般距离空间中设施定位问题,简称一般设施定位问题,借助集合覆盖问题,利用问题归约方法证明其不存在近似性能比小于1.243 0.316ln(ω-1)的多项式时间近似算法,除非NPDTIME(nO(log log n));设计了一般设施定位问题的局部搜索算法,证明算法近似性能比是(1 ω)/α,ω＞1,1≤α≤2.仿真实验表明,一般设施定位问题局部搜索算法的求解质量极高;通过实验进一步研究了该算法并给出了改进方法.
|
| 关 键 词： | 设施定位 计算复杂性 集合覆盖 近似算法 局部搜索 |
| 修稿时间： | 2006-06-01 |
Research on Computational Complexity and Approximation Algorithm for General Facility Location Problem |
| |
| Pan Rui,Zhu Daming,Ma Shaohan. Research on Computational Complexity and Approximation Algorithm for General Facility Location Problem[J]. Journal of Computer Research and Development, 2007, 44(5): 790-797 |
| |
| Authors: | Pan Rui Zhu Daming Ma Shaohan |
| |
| Affiliation: | School of Computer Science and Technology, Shandong University, Jinan 250061 |
| |
| Abstract: | |
| |
| Keywords: | facility location computational complexity set cover approximation algorithm local search |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
