Email this article An exact algorithm for finding a vector subset with the longest sum
- Authors: Shenmaier V.V.1
-
Affiliations:
- Sobolev Institute of Mathematics
- Issue: Vol 11, No 4 (2017)
- Pages: 584-593
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212936
- DOI: https://doi.org/10.1134/S1990478917040160
- ID: 212936
Cite item
Open Access
Access granted
Subscription Access
Abstract
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(nd−1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.
About the authors
V. V. Shenmaier
Sobolev Institute of Mathematics
Author for correspondence.
Email: shenmaier@mail.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090
