Enviar artigo por via de e-mail An exact algorithm for finding a vector subset with the longest sum
- Autores: Shenmaier V.V.1
-
Afiliações:
- Sobolev Institute of Mathematics
- Edição: Volume 11, Nº 4 (2017)
- Páginas: 584-593
- Seção: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212936
- DOI: https://doi.org/10.1134/S1990478917040160
- ID: 212936
Citar
Acesso aberto
Acesso está concedido
Somente assinantes
Resumo
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.
Palavras-chave
Sobre autores
V. Shenmaier
Sobolev Institute of Mathematics
Autor responsável pela correspondência
Email: shenmaier@mail.ru
Rússia, pr. Akad. Koptyuga 4, Novosibirsk, 630090
Arquivos suplementares
