Volume 15, No 6, 2008, P. 11-19
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
e-mail: gimadi@math.nsc.ru, artem@math.nsc.ru, rykov@math.nsc.ru
