Volume 15, No 4, 2008, P. 3043
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^{k1}$ 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
email: gimadi@math.nsc.ru, yg@ngs.ru, rykov@ledas.com
