Том 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 г.
Литература
[1] Кельманов А. В., Пяткин А. В. NP-полнота некоторых задач выбора подмножества векторов // Дискрет. анализ и исслед. операций. — 2010. — T. 17, №5. — С. 37–45.
[2] Edwards A. W. F., Cavalli–Sforza L. L. A method for cluster analysis // Biometrics. — 1965. — Vol. 21. — P. 362–375.
[3] Wirth H. Algorithms+data structures-programs. — New Jersey: Prentice Hall, 1976. — 366 p.
