An exact algorithm for finding a vector subset with the longest sum
Vladimir Shenmaier · Journal of Applied and Industrial Mathematics · 2017
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 + log n )). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.