|
This article is cited in 7 scientific papers (total in 7 papers)
An exact algorithm for finding a vector subset with the longest sum
V. V. Shenmaier Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
Abstract:
We consider the problem: Given a set of $n$ vectors in the $d$-dimensional Euclidean space, find a subset maximizing 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. Illustr. 2, bibliogr. 14.
Keywords:
sum vector, search for a vector subset, Euclidean space, polynomial-time algorithm, optimal solution.
Received: 22.05.2016 Revised: 10.05.2017
Citation:
V. V. Shenmaier, “An exact algorithm for finding a vector subset with the longest sum”, Diskretn. Anal. Issled. Oper., 24:4 (2017), 111–129; J. Appl. Industr. Math., 11:4 (2017), 584–593
Linking options:
https://www.mathnet.ru/eng/da885 https://www.mathnet.ru/eng/da/v24/i4/p111
|
Statistics & downloads: |
Abstract page: | 360 | Full-text PDF : | 172 | References: | 33 | First page: | 4 |
|