The Extraction of Maximal-Sum Principal Submatrix and Its Applications

Abstract

Extracting k-order maximal-sum principal submatrix from an n-order real matrix is a typical combinatorial optimization problem and an NP-hard problem. To improve the computational efficiency of solving this problem, we, in this paper, propose an accelerated algorithm with row-by-row updates, called the fusion row update accelerated algorithm, which works by reducing the number of addition operations for submatrix elements. The new algorithm is applied to accelerate color combination selection and maximize color difference, which improves the readability of data visualization results; it is also applied to accelerate stock investment portfolio selection and minimize correlation degree, which decreases the investment risk in the view of daily return volatility.

Keywords

• maximal-sum principal submatrix extraction
• maximum subarrays
• algorithm
• principal submatrix
• color combination selection
• stock investment portfolio selection