# zbMATH — the first resource for mathematics

On polynomial solvability of some problems of choosing a vector subset in a Euclidean space of fixed dimension. (Russian) Zbl 1249.90342
Summary: The problems under study are connected with the choice of a vector subset from a given finite set of vectors in the Euclidean space $$\mathbb R^k$$. The sum norm and the averaged square of the sum norm are considered as target functions (to be maximized). Optimal combinatorial algorithms with time complexity $$O(k^2 n^{2k})$$ are developed for these problems. Thus, the polynomial solvability of these problems is proved for fixed $$k$$.

##### MSC:
 90C60 Abstract computational complexity for mathematical programming problems
##### Keywords:
vector; Euclidean space; polynomial solvability