Аппроксимационная схема для одной задачи поиска подмножества векторов

Рассматривается следующая задача кластеризации: среди заданного множества векторов найти подмножество мощности $k$, обладающее минимальным квадратичным отклонением от своего среднего. Расстояния между векторами определяются евклидовой метрикой. Предлагается аппроксимационная схема (PTAS), позволяющая решать данную задачу с произвольной относительной погрешностью $\varepsilon$ за время $O(n^{2/\varepsilon+1}(9/\varepsilon)^{3/\varepsilon}d)$, где $n$ – число векторов в исходном множестве, $d$ – размерность пространства. Ил. 1, библиогр. 4.