Задача отыскания подмножества векторов с максимальным суммарным весом

Доказана NP-трудность дискретных оптимизационных задач, связанных с выбором из конечного семейства векторов в евклидовом пространстве подмножества векторов с максимальной нормой суммы. Предложены приближённые алгоритмы и получены оценки для относительной погрешности и временно́й сложности. В случае фиксированной размерности пространства построена полиномиальная аппроксимационная схема. Выделен подкласс задач, для которых за псевдополиномиальное время отыскивается точное решение. Полученные результаты могут быть использованы для решения задачи выбора фиксированного числа фрагментов в числовой последовательности квазипериодически повторяющегося фрагмента при заданном числе повторов.