Volume 16, No 6, 2009, P. 6873
UDC 519.2+621.391
A. V. Pyatkin
On the complexity of the maximum sum length vectors subset choice problem
Abstract:
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 NPhard if the dimension of the space is a part of input.
Bibl. 6.
Keywords: vectors sum problem, complexity, NPcompleteness.
Pyatkin Artyom Valer’evich ^{1,2}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2.
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
email: artem@math.nsc.ru
