On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension

摘要

The problems under study are connected with the choice of a vector subset from a given finite set of vectors in the Euclidean space ?~k. The sum norm and averaged square of the sumnorm are considered as the target functions (to be maximized). The optimal combinatorial algorithms with time complexity O(k~2n~(2k)) are developed for these problems. Thus, the polynomial solvability of these problems is proved for k fixed.