Аннотация:
Рассматривается следующая задача. Для заданного $n$-элементного множества векторов в $d$-мерном евклидовом пространстве найти подмножество, на котором достигается максимальное значение длины суммарного вектора. Предлагается алгоритм, позволяющий находить оптимальное решение этой задачи за время $O(n^{d-1}(d+\log n))$. В частности, если векторы входного множества лежат в одной плоскости, задача может быть решена за почти линейное время. Ил. 2, библиогр. 14.