Geodesic
The problem of finding a subset of vectors with the maximum total weight
Diskretnyj analiz i issledovanie operacij, Tome 14 (2007) no. 1, pp. 32-42

Voir la notice de l'article provenant de la source Math-Net.Ru

The NP-hardness is proved for the discrete optimization problems connected with maximizing the total weight of a subset of a finite set of vectors in Euclidean space, i.e., the Euclidean norm of the sum of the members. Two approximation algorithms are suggested, and the bounds for the relative error and time complexity are obtained. We give a polynomial approximation scheme in the case of a fixed dimension and distinguished a subclass of problems solvable in pseudopolynomial time. The results obtained are useful for solving the problem of choice of a fixed number of subsequences from a numerical sequence with a given number of quasiperiodical repetitions of the subsequence. 
@article{DA_2007_14_1_a1,
     author = {A. E. Baburin and E. Kh. Gimadi and N. I. Glebov and A. V. Pyatkin},
     title = {The problem of finding a subset of vectors with the maximum total weight},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {32--42},
     publisher = {mathdoc},
     volume = {14},
     number = {1},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2007_14_1_a1/}
}
TY  - JOUR
AU  - A. E. Baburin
AU  - E. Kh. Gimadi
AU  - N. I. Glebov
AU  - A. V. Pyatkin
TI  - The problem of finding a subset of vectors with the maximum total weight
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2007
SP  - 32
EP  - 42
VL  - 14
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2007_14_1_a1/
LA  - ru
ID  - DA_2007_14_1_a1
ER  - 
%0 Journal Article
%A A. E. Baburin
%A E. Kh. Gimadi
%A N. I. Glebov
%A A. V. Pyatkin
%T The problem of finding a subset of vectors with the maximum total weight
%J Diskretnyj analiz i issledovanie operacij
%D 2007
%P 32-42
%V 14
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2007_14_1_a1/
%G ru
%F DA_2007_14_1_a1
A. E. Baburin; E. Kh. Gimadi; N. I. Glebov; A. V. Pyatkin. The problem of finding a subset of vectors with the maximum total weight. Diskretnyj analiz i issledovanie operacij, Tome 14 (2007) no. 1, pp. 32-42. http://geodesic.mathdoc.fr/item/DA_2007_14_1_a1/