| K-median问题贪心近似算法的分析与实验 |
| |
| 引用本文： | 肖进杰,谢青松,刘晓华.K-median问题贪心近似算法的分析与实验[J].计算机工程,2008,34(22):213-214. |
| |
| 作者姓名： | 肖进杰 谢青松 刘晓华 |
| |
| 作者单位： | 山东工商学院信息与电子工程学院,烟台,264005 |
| |
| 摘 要： | 讨论K-median问题的贪心近似算法及其在实际计算中的表现。提出一个解K-median问题的贪心算法，证明该算法的近似度为O(ln(n/k))，通过实验证明该贪心算法在实际应用当中可以取得较好的效果，大约有90%的客户能被距离其最近、次近和第三近的设备服务。
|
| 关 键 词： | K-median问题 贪心算法 近似算法 |
| 修稿时间： | |
Analysis and Test of Approximation Greedy Algorithm for K-median Problems |
| |
| XIAO Jin-jie,XIE Qing-song,LIU Xiao-hua.Analysis and Test of Approximation Greedy Algorithm for K-median Problems[J].Computer Engineering,2008,34(22):213-214. |
| |
| Authors: | XIAO Jin-jie XIE Qing-song LIU Xiao-hua |
| |
| Affiliation: | (School of Information and Electronic Engineering, Shandong Institute of Business and Technology, Yantai 264005) |
| |
| Abstract: | This paper discusses approximation greedy algorithm for K-median and its property in actual computation. It presents a greedy algorithm for K-median and then proves that the approximation ratio of the greedy algorithm is at most O(ln(n/k)). The test data shows that the greedy algorithm can get good results in actual computation and about 90% clients can be serviced by the facility whose distance to the client is the 1st, 2nd, 3rd. |
| |
| Keywords: | K-median greedy algorithm approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
