Сложность и аппроксимация задачи о длиннейшем суммарном векторе

Для заданного конечного множества векторов в нормированном векторном пространстве рассматривается задача нахождения подмножества, на котором достигается максимальное значение нормы суммарного вектора. Показано, что в случае любой из норм $\ell_p$, $p\in[1,\infty)$, задача имеет порог неприближаемости в классе полиномиальных алгоритмов. Для задачи с произвольной нормой построена рандомизированная приближенная схема, эффективная в случае, когда размерность пространства равна $O(\log n)$. Библ. 19.