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

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