An exact algorithm for finding a vector subset with the longest sum

Аннотация

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d−1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.