Finding $k \times k$ rectangle in a matrix with maximum sum

Question

Given an $n \times n$ matrix $A$ with $0-1$ entries, I want to maximize $\sum\limits_{i \in I, j \in J} a_{ij}$ subject to $|I| = |J| = k.$

I expect the problem to be NP-hard, so I want a polynomial time approximation that gets you within a constant factor $c$ of the maximum the same way there is one for the cut norm, which is the same problem except we don't enforce $|I| = |J|.$

If $k \ge n/2,$ I can get $c \ge 1/2$ by taking the $k$ rows with maximum sum, then the $k$ subcolumns of those rows with maximum sum. In general, I can get $c \ge k/n.$

The following algorithm gets $c \ge 1/k$: For a list $L,$ let $f(L)$ be the sum of the $k$ largest entries of $L.$ Let the columns of $A$ be $a_1, \dots, a_n,$ pick $b_1, \dots, b_k$ for which $f(a_{b_i})$ are the largest $k$ values among $f(a_1), \dots, f(a_n),$ and then pick the $k$ subrows of $a_{b_1}, \dots, a_{b_k}$ with maximum sum.

Both the factors of $k/n, 1/k$ are tight as demonstrated by the worst case. Thus, we have an algorithm which is good unless $k = o(n),$ and one which is good when $k = o(1).$ What do we do about the middle, when $k = \sqrt{n}$ for example?

Answer 1

If you think of your matrix as the adjacency of a bipartite graph, where $a_{ij}=1$ if and only if vertices $i$ and $j$ are adjacent, your problem is very similar to the "Densest $k$-subgraph", where the goal is to find a subgraph with $k$ vertices maximizing the number of edges. In your case, to maximize $\sum\limits_{i \in I, j \in J} a_{ij}$ subject to $|I|+|J|=k$. This problem is NP-hard even on bipartite graph of maximum degree 3, by Feige and Seltser. See, for example, Andersen, Reid; Chellapilla, Kumar, Finding dense subgraphs with size bounds.

There are lots of inapproximability results for Densest $k$-subgraph for general graphs, but I do not know whether they still hold for bipartite graphs. Perhaps this survey is useful.

The case where one wants to decide if there are $I$ and $J$ with $|I|=|J|=k$ and $\sum\limits_{i \in I, j \in J} a_{ij} = k^2$ is sometimes called "Bipartite Clique" and is also hard (e.g., Khot, Subhash, Ruling out PTAS for graph min-bisection, dense (k)-subgraph, and bipartite clique).