Аннотация:
В работе рассматривается задача кластеризации $N$-элементного множества
точек в $d$-мерном евклидовом пространстве на два кластера. В этой задаче требуется найти
$2$-разбиение,
минимизирующее сумму (по обоим кластерам) внутрикластерных квадратичных разбросов точек относительно
искомых центров. Центр одного кластера определяется как
центроид (геометрический центр), а центр другого кластера
является искомой точкой во входном множестве. Анализируется вариант
задачи, в котором размеры (т. е. мощности) кластеров заданы, а их суммарный
размер совпадает с размером входного множества. Доказано,
что задача NP-трудна в сильном смысле. Установлено, что для нее не существует
полностью полиномиальной аппроксимационной схемы, если P$\neq$ NP.
Ключевые слова:евклидово пространство, кластеризация, $2$-разбиение, квадратичный разброс, центр, центроид, медиана, сильная NP-трудность, несуществование полностью полиномиальной приближенной схемы, эффективная сводимость с сохранением точности.