Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности

Рассматривается NP-трудная в сильном смысле задача разбиения конечной последовательности точек евклидова пространства на два кластера заданных мощностей по критерию минимума суммы по обоим кластерам внутрикластерных сумм квадратов расстояний от элементов кластеров до их центров. Центр одного из кластеров неизвестен и определяется как среднее значение по всем точкам, образующим этот кластер. Центр второго кластера задан в начале координат. При этом разность между номерами последующего и предыдущего элементов последовательности, входящих в первый кластер, ограничена сверху и снизу заданными константами. Предложен рандомизированный алгоритм, который при заданных относительной погрешности и вероятности несрабатывания для установленного значения параметра находит приближëнное решение задачи за полиномиальное время. Найдены условия, при которых алгоритм полиномиален и асимптотически точен. Библ. 19.