Volume 16, No 6, 2009, P. 68-73
A. V. Pyatkin
On the complexity of the maximum sum length vectors subset choice problem
The maximum sum length vectors subset choice problem is considered. In the case of the fixed dimension of the space this problem is polynomially solvable. It is proved that the problem is NP-hard if the dimension of the space is a part of input.
Keywords: vectors sum problem, complexity, NP-completeness.
Pyatkin Artyom Valer’evich 1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia