Рандомизированные алгоритмы для некоторых труднорешаемых задач кластеризации конечного множества точек евклидова пространства

Рассматриваются две NP-трудные в сильном смысле задачи кластеризации конечного множества точек евклидова пространства. Во входном множестве первой задачи требуется найти кластер (подмножество) заданной мощности, минимизирующий сумму квадратов расстояний между элементами этого кластера и его центроидом (геометрическим центром). Каждая точка вне этого кластера рассматривается как одноэлементный кластер. Во второй задаче требуется найти разбиение входного множества на два кластера, минимизирующее сумму по обоим кластерам взвешенных внутрикластерных сумм квадратов расстояний между элементами кластеров и их центрами. Центр одного из кластеров неизвестен и определяется как его центроид, а центр второго кластера задан в некоторой точке пространства (без ограничения общности этой точкой является начало координат). Весовыми множителями внутрикластерных сумм являются заданные мощности искомых кластеров. Для обеих задач предложены рандомизированные параметризованные алгоритмы. Для заданных верхних границ относительной ошибки и вероятности несрабатывания определено значение параметра, при котором алгоритмы находят приближенные решения задач за полиномиальное время. Это время линейно зависит как от размерности пространства, так и от мощности входного множества. Найдены условия, при которых оба алгоритма находят асимптотически точные решения и имеют трудоемкость, линейно зависящую от размерности пространства и квадратично — от мощности входного множества. Библ. 27.