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