Geodesic
A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 3, pp. 5-17

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

We present a randomized approximation algorithm for the problem of finding a subset of a finite set of vectors in the Euclidean space with the maximal norm of the sum vector. We show that with an appropriate choice of parameters, the algorithm is polynomial for the problem with any fixed dimension and asymptotically optimal. Il. 1, bibliogr. 18.
Keywords: search for vector subset, randomized algorithm, asymptotical exactness. 
@article{DA_2015_22_3_a0,
     author = {E. Kh. Gimadi and I. A. Rykov},
     title = {A randomized algorithm for the vector subset problem with the maximal {Euclidean} norm of its sum},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--17},
     publisher = {mathdoc},
     volume = {22},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_3_a0/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - I. A. Rykov
TI  - A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 5
EP  - 17
VL  - 22
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_3_a0/
LA  - ru
ID  - DA_2015_22_3_a0
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A I. A. Rykov
%T A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 5-17
%V 22
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_3_a0/
%G ru
%F DA_2015_22_3_a0
E. Kh. Gimadi; I. A. Rykov. A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 3, pp. 5-17. http://geodesic.mathdoc.fr/item/DA_2015_22_3_a0/