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

Анализируется статус вычислительной сложности нескольких известных дискретных экстремальных задач с измененным направлением оптимизации, а именно: c $\max$ на $\min$. Рассматриваются евклидовы задачи поиска подмножества в конечном множестве точек (векторов). В этих задачах целевые функции зависят либо только от нормы суммы элементов подмножества, либо от этой нормы и мощности искомого подмножества. Доказано, что если размерность пространства является частью входа, то все рассмотренные задачи $\mathrm{NP}$-трудны в сильном смысле. Установлено, что при фиксированной размерности пространства все задачи $\mathrm{NP}$-трудны даже в двумерном случае (на плоскости) и для них не существует приближенных алгоритмов с гарантированной оценкой точности, если $\mathrm{P\ne NP}$. Показано, что если координаты входных точек целочисленны, то все задачи разрешимы за псевдополиномиальное время в случае, когда размерность пространства фиксирована. Библ. 17.