Том 17, номер 5, 2010 г., Стр. 37-45

УДК 519.2+621.391
Кельманов А. В., Пяткин А. В.
NP-полнота некоторых задач выбора подмножества векторов

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

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

Кельманов Александр Васильевич ^1,2
Пяткин Артём Валерьевич ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: kelm@math.nsc.ru, artem@math.nsc.ru

Статья поступила 12 апреля 2010 г.
Исправленный вариант — 6 июля 2010 г.