K-center算法笔记

分类: 文章 • 2023-03-29 18:35:44

K-center问题

K-center算法笔记
黑色方块代表输入的点，蓝色圆点则是k-center问题中需要寻找的center。
k-center：寻找k个半径越小越好的center以覆盖所有的点。
其中，定义distance matric为

定义好距离之后，K-center就可以表示为如下优化

K-center贪婪算法伪码