А. В. Кельманов, А. В. Пяткин, “NP-полнота некоторых задач выбора подмножества векторов”, Дискретн. анализ и исслед. опер., 2010, том 17, выпуск 5,страницы 37

Эта публикация цитируется в 40 статьях

NP-полнота некоторых задач выбора подмножества векторов

А. В. Кельманов^ab, А. В. Пяткин^ab

^a Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Россия
^b Новосибирский гос. университет, Новосибирск, Россия

Аннотация: Доказана NP-полнота некоторых задач выбора подмножества векторов евклидова пространства. К решению таких задач сводится одна из проблем анализа данных. Предполагается, что искомое подмножество имеет фиксированную мощность и включает векторы, “близкие” между собой по критерию минимума суммы квадратов расстояний. Библиогр. 13.

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

УДК: 519.2+621.391

Статья поступила: 12.04.2010
Переработанный вариант: 06.07.2010