求解k(《n)-中心问题的快速算法

摘要：

提出求解k(＜n)-中心问题的两类算法,其中第1类算法适用于k＜10的情况,而第2类算法可应用于10＜k＜n的情况 .两类算法的思想不同,前者利用等分凸壳直径的方法并且所确定的圆的圆心位置是固定的,而后者采用多种参数随机化的方法,从而圆心是不确定的 .此外证明了算法的正确性并且分析了算法的复杂性 .

关键词：k-中心问题、凸壳、算法、时间复杂性

所属期刊栏目：41

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2004-06-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：743-748