| k-median问题反向贪心随机算法 |
| |
| 引用本文： | 王守强.k-median问题反向贪心随机算法[J].计算机科学,2012,39(7):232-236. |
| |
| 作者姓名： | 王守强 |
| |
| 作者单位： | 山东交通学院信息科学与电气工程学院 济南250023 |
| |
| 基金项目： | 国家自然科学基金，山东交通学院自然科学基金项目，山东交通学院博士启动基金 |
| |
| 摘 要： | k-median问题的近似算法研究一直是计算机科学工作者关注的焦点。基于均衡限制条件,利用反向贪心策略,给出求解该问题的随机近似算法。证明该算法以较大的概率满足其近似性能比的期望值为(3+O(ln(ln(k)/α))。该算法的时间复杂度为O(kαln(k)]2(n+m)),其中n和m分别代表设施集合以及客户点集的大小。最后,通过计算机实验验证了k-median问题的反向贪心算法的实际计算效果。
|
| 关 键 词： | k-median 随机算法 反向贪心 近似性能比 |
Randomized Reverse Greedy Algorithm for k-median Problem |
| |
| WANG Shou-qiang.Randomized Reverse Greedy Algorithm for k-median Problem[J].Computer Science,2012,39(7):232-236. |
| |
| Authors: | WANG Shou-qiang |
| |
| Affiliation: | WANG Shou-qiang(Department of Information Engineering,Shandong Jiaotong University,Jinan 250023,China) |
| |
| Abstract: | |
| |
| Keywords: | k- median Randomized algorithm Reverse greedy Aapproximation ratio |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
