Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера

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