EN|RU

Том 19, номер 2, 2012 г., Стр. 93-101

УДК 519.176
Шенмайер В. В. 
Аппроксимационная схема для одной задачи поиска подмножества векторов

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

Ключевые слова: выбор подмножества векторов, кластерный анализ, аппроксимационная схема, приближенный алгоритм.

Шенмайер Владимир Владимирович 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: shenmaier@mail.ru

Статья поступила 15 июня 2011 г.
Исправленный вариант — 8 сентября 2011 г.

 © Институт математики им. С. Л. Соболева, 2015