On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension |
| |
| Authors: | E Kh Gimadi A V Pyatkin I A Rykov |
| |
| Institution: | (1) Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, NT, Hong Kong;(2) Department of Management Science, School of Management, Fudan University, Shanghai, 200433, P. R. China;(3) Department of Automation, Shanghai University, Shanghai, 200072, China;(4) Department of Applied Mathematics, Shanghai University of Finance and Economics, Shanghai, 200433, P. R. China |
| |
| 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: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
