$2$-приближенный алгоритм для одной задачи поиска семейства непересекающихся подмножеств векторов

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

Статья представлена к публикации членом редколлегии: А. И. Кибзун