On two problems of choosing some subset of vectors with integer coordinates that has maximum norm of the sum of elements in Euclidean space

Autor: E. Kh. Gimadi, Yu. V. Glazkov, Ivan A. Rykov
Rok vydání: 2009
Předmět:
Zdroj: Journal of Applied and Industrial Mathematics. 3:343-352
ISSN: 1990-4797
1990-4789
DOI: 10.1134/s1990478909030041
Popis: Under study are the two problems of choosing a subset of m vectors with the maximum norm of the sum of the elements from a set of n vectors in Euclidean space ℝ k . The vectors are assumed to have integer coordinates. Using the dynamic programming technique, some new optimal algorithms are suggested for solving the problems; these algorithms have pseudopolynomial time when the dimension of the space is fixed. The new algorithms have certain advantages over the availables: the vector subset problem can be solved faster for m < (k/2) k , while, after taking into account an additional restriction on the order of the vectors, the time complexity is k k−1 times less independently on m.
Databáze: OpenAIRE
Externí odkaz: