通信学报

• • 上一篇    下一篇

基于最小聚类求解k-means问题算法

王守强,朱大铭   

  • 出版日期:2010-07-25 发布日期:2010-07-15

  • Online:2010-07-25 Published:2010-07-15

摘要: 针对每个划分子集要求至少满足一定数量点的k-means问题,设计了该问题的随机近似算法。1)给出一个样本子集,证明了该样本子集至少以1/2的概率包含每个最优子集中至少一个点,进一步设计近似度为2的随机算法。2) 设计了该问题的(1+e)随机近似算法,算法的成功概率至少为3/2k+2。3) 利用取样技术,设计了k-means问题的局部搜索随机算法。

No Suggested Reading articles found!