Given a $n \times n$ matrix $M$ of positive integers and a constant $d$. If $R,C \subset \{1,...,n\} $ let $$S_M(R,C) = \sum_{r \in R,c \in C }M_{i,j} $$
I want to find the sets $$R,C \subset \{1,...,n\}, |R|,|C| = d $$ such that $S_M(R,C)$ is as big as possible.
I suspect this to be a known problem. I am wondering if anyone has seen this before and can point me towards research papers on this problem
It is NP-hard, by reduction from the maximum balanced biclique problem.
Suppose you have a bipartite graph $G$, and the goal is to test whether there is a balanced biclique of size $d$. Let $M$ denote the adjacency matrix of $G$. Then there is a balanced biclique of size $d$ iff the maximum sum in your problem is $d^2$. Therefore, any algorithm for your problem would immediately yield an algorithm for the maximum balanced biclique problem.
In practice, one approach is try to solve it with integer linear programming or with a SAT solver.
