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

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?

• I'm assuming the value $k$ is also part of the input?
– a3nm
Jul 28 at 14:49
• @a3nm That's correct. Jul 29 at 15:55

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).