|
Дискретный анализ и исследование операций, 2010, том 17, выпуск 5, страницы 37–45
(Mi da623)
|
|
|
|
Эта публикация цитируется в 40 научных статьях (всего в 40 статьях)
NP-полнота некоторых задач выбора подмножества векторов
А. В. Кельмановab, А. В. Пяткинab a Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Россия
b Новосибирский гос. университет, Новосибирск, Россия
Аннотация:
Доказана NP-полнота некоторых задач выбора подмножества векторов евклидова пространства. К решению таких задач сводится одна из проблем анализа данных. Предполагается, что искомое подмножество имеет фиксированную мощность и включает векторы, “близкие” между собой по критерию минимума суммы квадратов расстояний. Библиогр. 13.
Ключевые слова:
выбор подмножества векторов, кластерный анализ, алгоритмическая сложность, NP-полнота.
Статья поступила: 12.04.2010 Переработанный вариант: 06.07.2010
Образец цитирования:
А. В. Кельманов, А. В. Пяткин, “NP-полнота некоторых задач выбора подмножества векторов”, Дискретн. анализ и исслед. опер., 17:5 (2010), 37–45; J. Appl. Industr. Math., 5:3 (2011), 352–357
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da623 https://www.mathnet.ru/rus/da/v17/i5/p37
|
Статистика просмотров: |
Страница аннотации: | 680 | PDF полного текста: | 250 | Список литературы: | 75 | Первая страница: | 3 |
|