EN|RU Volume 15, No 4, 2008, P. 30-43 UDC 519.8 E. Kh. Gimadi, Ju. V. Glazkov, I. A. Rykov The vector subset problem with integer coordinates in euclidean space with the maximum sum Abstract: 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, pseudopolynomial algorithm, dynamic programming. Gimadi Edvard Khairutdinovich 1 Glazkov Jurii Vladimirovich 1 Rykov Ivan Aleksandrovich 1 1. S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia e-mail: gimadi@math.nsc.ru, yg@ngs.ru, rykov@ledas.com © Sobolev Institute of Mathematics, 2015