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

摘要

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