EN|RU

Том 19, номер 3, 2012 г., Стр. 27-38

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

Аннотация:
Рассматриваются некоторые труднорешаемые задачи поиска подпоследовательности в последовательности векторов евклидова пространства, состоящей из конечного числа членов. Предполагается, что искомая подпоследовательность содержит фиксированное число векторов, близких между собой по критерию минимума суммы квадратов расстояний, причем поиск векторов подчинён условию: разность между номерами последующего и предыдущего искомых векторов ограничена сверху и снизу некоторыми константами. Предложены 2-приближенные эффективные алгоритмы решения этих задач.
Библиогр. 11.

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

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

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

Статья поступила 11 августа 2011 г.
Исправленный вариант — 7 ноября 2011 г.

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