Точные псевдополиномиальные алгоритмы для задачи сбалансированной $2$-кластеризации

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