Volume 15, No 6, 2008, P. 1119
UDC 519.8519.8519.8
E. Kh. Gimadi, A. V. Pyatkin, I. A. Rykov
On polynomial solvability of some vector subset problems in euclidean space with fixed dimension
Abstract:
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.
Gimadi Edward Khairutdinovich ^{1}
Pyatkin Artem Valerievich ^{1}
Rykov Ivan Alexandrovich ^{1}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
email: gimadi@math.nsc.ru, artem@math.nsc.ru, rykov@math.nsc.ru
