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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2008},
     volume = {15},
     number = {6},
     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
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
%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/

[1] 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

[2] Gimadi E. Kh., Glazkov Yu. V., Rykov I. A., “O dvukh zadachakh vybora podmnozhestva vektorov s tselochislennymi koordinatami s maksimalnoi normoi summy v evklidovom prostranstve”, Diskret. analiz i issled. operatsii, 15:4 (2008), 30–43

[3] 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

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

[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

[6] Baburin A. E., Gimadi E. Kh., Glebov N. I., Pyatkin A. V., “The problem of finding a subset of vectors with the maximum total weight”, J. Appl. Industr. Math., 2:1 (2008), 32–38 | MR