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\).

90C60 Abstract computational complexity for mathematical programming problems