An exact algorithm for finding a vector subset with the longest sum |
| |
Authors: | V V Shenmaier |
| |
Institution: | 1.Sobolev Institute of Mathematics,Novosibirsk,Russia |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|