Том 17, номер 2, 2010 г., Стр. 39-45

УДК 519.2+621.391
Долгушев А. В., Кельманов А. В.
К вопросу об алгоритмической сложности одной задачи кластерного анализа

Аннотация:
Доказана NP-полнота задачи MSSC —кластеризации множества векторов евклидова пространства по критерию минимума суммы квадратов —для случая, когда размерность пространства является, а число кластеров не является частью входа задачи.
Библиогр. 9.

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

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

Статья поступила 1 декабря 2009 г.
Исправленный вариант — 17 декабря 2009 г.