Geodesic
The vector subset problem with integer coordinates in Euclidean space with the maximum sum
Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 4, pp. 30-43.

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

Two problems of selecting a subset of $m$ vectors with the maximum norm of sum from a set of $n$ vectors in Euclidean space $\mathbb R^k$ is considered. It is supposed that the coordinates of the vectors are integer. Using the dynamic programming technique new optimal algorithms are constructed. They have pseudopolynomial complexity, when the dimension $k$ of the vector space is fixed. New algorithms have certain advantages (with respect to earlier known algorithms): the vector subset problem can be solved faster, if $m(k/2)^k$, and the time complexity is $k^{k-1}$ times less for the problem with an additional restriction on the order of vectors independently of $m$. Bibl. 5.
Keywords: subset selection, Euclidian metric, time complexity, dynamic programming.
Mots-clés : pseudopolynomial algorithm 
@article{DA_2008_15_4_a2,
     author = {E. Kh. Gimadi and Yu. V. Glazkov and I. A. Rykov},
     title = {The vector subset problem with integer coordinates in {Euclidean} space with the maximum sum},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {30--43},
     publisher = {mathdoc},
     volume = {15},
     number = {4},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2008_15_4_a2/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - Yu. V. Glazkov
AU  - I. A. Rykov
TI  - The vector subset problem with integer coordinates in Euclidean space with the maximum sum
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2008
SP  - 30
EP  - 43
VL  - 15
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2008_15_4_a2/
LA  - ru
ID  - DA_2008_15_4_a2
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A Yu. V. Glazkov
%A I. A. Rykov
%T The vector subset problem with integer coordinates in Euclidean space with the maximum sum
%J Diskretnyj analiz i issledovanie operacij
%D 2008
%P 30-43
%V 15
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2008_15_4_a2/
%G ru
%F DA_2008_15_4_a2
E. Kh. Gimadi; Yu. V. Glazkov; I. A. Rykov. The vector subset problem with integer coordinates in Euclidean space with the maximum sum. Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 4, pp. 30-43. http://geodesic.mathdoc.fr/item/DA_2008_15_4_a2/

[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), 22–32 | 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., “Zadacha vybora podmnozhestva vektorov s maksimalnoi summoi”, Materialy Rossiiskoi konferentsii “Diskretnaya optimizatsiya i issledovanie operatsii” (Vladivostok, 7–14 sentyabrya 2007), Izd-vo In-ta matematiki, Novosibirsk, 2007, 27–30

[4] Gimadi E. Kh., Kelmanov A. V., Kelmanova M. A., Khamidullin S. A., “Aposteriornoe obnaruzhenie v chislovoi posledovatelnosti kvaziperiodicheski povtoryayuschegosya fragmenta pri zadannom chisle povtorov”, Sib. zhurn. industr. matematiki, 9:1 (2006), 55–74 | MR

[5] Kelmanov A. V., Khamidullin S. A., Okolnishnikova L. V., “Aposteriornoe obnaruzhenie odinakovykh podposledovatelnostei-fragmentov v kvaziperiodicheskoi posledovatelnosti”, Sib. zhurn. industr. matematiki, 5:2 (2002), 94–108 | MR