Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации

Рассматривается $\mathrm{NP}$-трудная в сильном смысле задача разбиения конечного множества точек евклидова пространства на два кластера заданных размеров по критерию минимума суммы по обоим кластерам сумм квадратов внутрикластерных расстояний от элементов кластеров до их центров. Предполагается, что центр одного из искомых кластеров задан в желаемой (произвольной) точке пространства (без ограничения общности — в начале координат), а центр другого неизвестен и определяется как среднее значение по всем элементам, образующим этот кластер. Установлено, что для этой задачи не существует полностью полиномиальной приближенной схемы, если $\mathrm{P\ne NP}$, и такая схема обоснована для случая, когда размерность пространства фиксирована. Библ. 29.