Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов

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