RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2011, том 18, выпуск 1, страницы 61–69 (Mi da638)

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

Приближённый алгоритм решения одной задачи поиска подмножества векторов

А. В. Кельмановab, С. М. Романченкоb

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

Аннотация: Одна из проблем анализа данных сводится к решению NP-трудной экстремальной задачи поиска в множестве векторов евклидова пространства подмножества, имеющего заданную мощность и включающего векторы, “близкие” между собой по критерию минимума суммы квадратов расстояний. В работе обоснован полиномиальный 2-приближённый алгоритм решения этой задачи. Библиогр. 3.

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

УДК: 519.2+621.391

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


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2012, 6:1, 90–96

Реферативные базы данных:


© МИАН, 2024