Geodesic
On the complexity of the maximum sum length vectors subset choice problem
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 6, pp. 68-73 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. Bibl. 6.
Keywords: vectors sum problem, complexity, NP-completeness. 
@article{DA_2009_16_6_a5,
     author = {A. V. Pyatkin},
     title = {On the complexity of the maximum sum length vectors subset choice problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {68--73},
     year = {2009},
     volume = {16},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_6_a5/}
}
TY  - JOUR
AU  - A. V. Pyatkin
TI  - On the complexity of the maximum sum length vectors subset choice problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 68
EP  - 73
VL  - 16
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_6_a5/
LA  - ru
ID  - DA_2009_16_6_a5
ER  - 
%0 Journal Article
%A A. V. Pyatkin
%T On the complexity of the maximum sum length vectors subset choice problem
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 68-73
%V 16
%N 6
%U http://geodesic.mathdoc.fr/item/DA_2009_16_6_a5/
%G ru
%F DA_2009_16_6_a5
A. V. Pyatkin. On the complexity of the maximum sum length vectors subset choice problem. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 6, pp. 68-73. http://geodesic.mathdoc.fr/item/DA_2009_16_6_a5/

[1] Baburin A. E., Gimadi E. Kh., Glebov N. I., Pyatkin A. V., “Zadacha otyskaniya podmnozhestva vektorov s maksimalnym summarnym vesom”, Diskret. analiz i issled. operatsii. Ser. 2, 14:1 (2007), 32–42 | MR

[2] Baburin A. E., Pyatkin A. V., “O polinomialnykh algoritmakh resheniya odnoi zadachi summirovaniya vektorov”, Diskret. analiz i issled. operatsii. Ser. 1, 13:2 (2006), 3–10 | MR

[3] Gimadi E. Kh., Pyatkin A. V., Rykov I. A., “O polinomialnoi razreshimosti nekotorykh zadach vybora podmnozhestva vektorov v evklidovom prostranstve fiksirovannoi razmernosti”, Diskret. analiz i issled. operatsii, 15:6 (2008), 11–19 | MR

[4] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[5] Kadets M. I., “Ob odnom svoistve vektornykh lomanykh v $n$-mernom prostranstve”, Uspekhi mat. nauk, 8:1 (1953), 139–143 | MR | Zbl

[6] Kelmanov A. V., Pyatkin A. V., “Ob odnom variante zadachi vybora podmnozhestva vektorov”, Diskret. analiz i issled. operatsii, 15:5 (2008), 20–34 | MR