On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension
- 1 January 2010
- journal article
- Published by Pleiades Publishing Ltd in Journal of Applied and Industrial Mathematics
- Vol. 4 (1), 48-53
- https://doi.org/10.1134/s1990478910010084
Abstract
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 2 n 2k ) are developed for these problems. Thus, the polynomial solvability of these problems is proved for k fixed.Keywords
This publication has 4 references indexed in Scilit:
- On a version of the problem of choosing a vector subsetJournal of Applied and Industrial Mathematics, 2009
- On two problems of choosing some subset of vectors with integer coordinates that has maximum norm of the sum of elements in Euclidean spaceJournal of Applied and Industrial Mathematics, 2009
- The problem of finding a subset of vectors with the maximum total weightJournal of Applied and Industrial Mathematics, 2008
- Polynomial algorithms for solving the vector sum problemJournal of Applied and Industrial Mathematics, 2007