A polynomial case of cardinality constrained quadratic optimization problem

摘要

We investigate in this paper a fixed parameter polynomial algorithm for cardinality constrained quadratic optimization problem, which is NP-hard in general. More specifically, we prove that, given a problem of size n, the number of decision variables, and s, the cardinality, if, for some 0＜k ≤ n, the n - k largest eigenvalues of the coefficient matrix of the problem are identical, we can construct a solution algorithm with computational complexity of (O)(n2k), which is independent of the cardinality s. Our main idea is to decompose the primary problem into several convex subproblems, while the total number of the subproblems is determined by the number of cells generated by a corresponding hyperplane arrangement in (R)k space.