Аппроксимируемость задачи о подмножестве векторов с суммой максимальной длины

Рассматривается задача выбора подмножества векторов с суммой максимальной длины. Дан ответ на вопрос о существовании полиномиальных приближённых алгоритмов, позволяющих решать эту задачу с константной точностью при нефиксированной размерности пространства. Установлено, что в случае евклидовых пространств рассматриваемая задача разрешима за полиномиальное время с точностью $\sqrt\alpha,$ где $\alpha=2/\pi$, и при условии $\mathrm P\neq\mathrm{NP}$ не существует полиномиальных алгоритмов с лучшей точностью. Показано, что в случае пространств с нормой $\ell_p$ задача APX-полна, если $p\in[1,2]$, и не аппроксимируема с константной точностью, если $\mathrm P\neq\mathrm{NP}$ и $p\in(2,\infty)$. Табл. 1, библиогр. 21.