0
$\begingroup$

I have a matrix, which has N rows and M columns. I need to find n rows and m columns, which has the highest sum. Matrix consists of positive numbers. Not optimal solutions are ok. For example N=M=4; n=m=3

A=$\begin{bmatrix}13 & 83 & 93 & 1 \\70 & 84 & 37 & 38 \\24 & 68 & 78 & 25 \\30 & 47 & 87 & 89\end{bmatrix}$

The highest sum (571) is by removing 1st row and 0th column. Currently I take first n rows by sum and m first columns by sum within current n rows. What alternative methods could I use?

$\endgroup$
  • $\begingroup$ I don't understand well your current method. Are you selecting greedily the rows first ? Which may be not optimal of course. $\endgroup$ – Optidad Jun 27 '19 at 11:51
  • $\begingroup$ Your problem is NP-complete. Consider the adjacency matrix $A$ of an unweighted graph $G=(V,E)$ so that $N=M=|V|$. Choose a parameter $k$ and let $n=m=k$. There is a $n \times m$ submatrix $B$ of $I+A$ whose elements sum to at least $k^2$ iff $G$ contains a clique of size $k$. $\endgroup$ – Steven Jun 27 '19 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.