Том 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. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: shenmaier@mail.ru

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

Литература

[1] Кельманов А. В., Пяткин А. В. NP-полнота некоторых задач выбора подмножества векторов // Дискрет. анализ и исслед. операций. — 2010. — T. 17, № 5. — С. 37—45.

[2] Кельманов А. В., Романченко С. М. Приближённый алгоритм решения одной задачи поиска подмножества векторов // Дискрет. анализ и исслед. операций. — 2011. — Т. 18, № 1. — С. 61–69.

[3] Кельманов А. В., Романченко С. М. Псевдополиномиальные алгоритмы для некоторых задач поиска подмножества векторов и кластерного анализа // Автоматика и телемеханика. — 2011. — В печати.

[4] Wirth Н. Algorithms + data structures = programs // New Jersey: Prentice Hall, 1976. — 366 p.