On polynomial solvability of some problems of choosing a vector subset in a Euclidean space of fixed dimension. (Russian) Zbl 1249.90342

Gimadi, Eh. Kh.; Pyatkin, A. V.; Rykov, I. A.

Diskretn. Anal. Issled. Oper. 15, No. 6, 11-19 (2008).

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