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.

Key words: K-median, greedy algorithm, approximation algorithm

摘要： 讨论K-median问题的贪心近似算法及其在实际计算中的表现。提出一个解K-median问题的贪心算法，证明该算法的近似度为O(ln(n/k))，通过实验证明该贪心算法在实际应用当中可以取得较好的效果，大约有90%的客户能被距离其最近、次近和第三近的设备服务。

关键词: K-median问题, 贪心算法, 近似算法

CLC Number: 

• TP311