Geodesic
On polynomial solvability of some vector subset problems in Euclidean space with fixed dimension
Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 6, pp. 11-19

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

Problems of choosing vectors in the multidimensional Euclidean space $\mathbb R^k$ are considered. The maximum norm of sum or the averaged square of the norm are considered as the problem objective. We present combinatorial algorithms with time complexity $O(k^2n^{2k})$. Thereby it is shown that the considered problems are polynomially solvable for fixed dimension of space $\mathbb R^k$. Bibl. 6.
Keywords: vector subset, Euclidean space, polynomial solvability. 
@article{DA_2008_15_6_a1,
     author = {E. Kh. Gimadi and A. V. Pyatkin and I. A. Rykov},
     title = {On polynomial solvability of some vector subset problems in {Euclidean} space with fixed dimension},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {11--19},
     publisher = {mathdoc},
     volume = {15},
     number = {6},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2008_15_6_a1/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - A. V. Pyatkin
AU  - I. A. Rykov
TI  - On polynomial solvability of some vector subset problems in Euclidean space with fixed dimension
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2008
SP  - 11
EP  - 19
VL  - 15
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2008_15_6_a1/
LA  - ru
ID  - DA_2008_15_6_a1
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A A. V. Pyatkin
%A I. A. Rykov
%T On polynomial solvability of some vector subset problems in Euclidean space with fixed dimension
%J Diskretnyj analiz i issledovanie operacij
%D 2008
%P 11-19
%V 15
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2008_15_6_a1/
%G ru
%F DA_2008_15_6_a1
E. Kh. Gimadi; A. V. Pyatkin; I. A. Rykov. On polynomial solvability of some vector subset problems in Euclidean space with fixed dimension. Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 6, pp. 11-19. http://geodesic.mathdoc.fr/item/DA_2008_15_6_a1/