EN|RU

Том 18, номер 1, 2011 г., Стр. 61-69

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

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

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

Кельманов Александр Васильевич 1,2
Романченко Семен Михайлович 2

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

Статья поступила 26 июля 2010 г.
Исправленный вариант — 9 октября 2010 г.

 © Институт математики им. С. Л. Соболева, 2015