<p>If you think of your matrix as the adjacency of a bipartite graph, where <span class="math-container">$a_{ij}=1$</span> if and only if vertices <span class="math-container">$i$</span> and <span class="math-container">$j$</span> are adjacent, your problem is very similar to the &quot;Densest <span class="math-container">$k$</span>-subgraph&quot;, where the goal is to find a subgraph with <span class="math-container">$k$</span> vertices maximizing the number of edges. In your case, to maximize <span class="math-container">$\sum\limits_{i \in I, j \in J} a_{ij}$</span> subject to <span class="math-container">$|I|+|J|=k$</span>. This problem is NP-hard even on bipartite graph of maximum degree 3, by Feige and Seltser. See, for example,
<em>Andersen, Reid; Chellapilla, Kumar</em>, <a href="https://doi.org/10.1007/978-3-540-95995-3_3" rel="nofollow noreferrer"><strong>Finding dense subgraphs with size bounds</strong></a>.</p>
<p>There are lots of inapproximability results for Densest <span class="math-container">$k$</span>-subgraph for general graphs, but I do not know whether they still hold for bipartite graphs. Perhaps <a href="https://arxiv.org/abs/2303.14467" rel="nofollow noreferrer">this survey</a> is useful.</p>
<p>The case where one wants to decide if there are <span class="math-container">$I$</span> and <span class="math-container">$J$</span> with <span class="math-container">$|I|=|J|=k$</span> and <span class="math-container">$\sum\limits_{i \in I, j \in J} a_{ij} = k^2$</span>  is sometimes called &quot;Bipartite Clique&quot; and is also hard (e.g., <em>Khot, Subhash</em>, <a href="https://doi.org/10.1137/S0097539705447037" rel="nofollow noreferrer"><strong>Ruling out PTAS for graph min-bisection, dense (k)-subgraph, and bipartite clique</strong></a>).</p>

CC BY-SA 4.0
2023-08-05T02:22:30.020Z
2023-08-05T02:22:30.020Z
Vinicius dos Santos
<p>Given an <span class="math-container">$n \times n$</span> matrix <span class="math-container">$A$</span> with <span class="math-container">$0-1$</span> entries, I want to maximize <span class="math-container">$\sum\limits_{i \in I, j \in J} a_{ij}$</span> subject to <span class="math-container">$|I| = |J| = k.$</span></p>
<p>I expect the problem to be NP-hard, so I want a polynomial time approximation that gets you within a constant factor <span class="math-container">$c$</span> of the maximum the same way there is <a href="https://web.math.princeton.edu/%7Enaor/homepage%20files/cutnorm.pdf" rel="noreferrer">one</a> for the cut norm, which is the same problem except we don't enforce <span class="math-container">$|I| = |J|.$</span></p>
<p>If <span class="math-container">$k \ge n/2,$</span> I can get <span class="math-container">$c \ge 1/2$</span> by taking the <span class="math-container">$k$</span> rows with maximum sum, then the <span class="math-container">$k$</span> subcolumns of those rows with maximum sum. In general, I can get <span class="math-container">$c \ge k/n.$</span></p>
<p>The following algorithm gets <span class="math-container">$c \ge 1/k$</span>: For a list <span class="math-container">$L,$</span> let <span class="math-container">$f(L)$</span> be the sum of the <span class="math-container">$k$</span> largest entries of <span class="math-container">$L.$</span> Let the columns of <span class="math-container">$A$</span> be <span class="math-container">$a_1, \dots, a_n,$</span> pick <span class="math-container">$b_1, \dots, b_k$</span> for which <span class="math-container">$f(a_{b_i})$</span> are the largest <span class="math-container">$k$</span> values among <span class="math-container">$f(a_1), \dots, f(a_n),$</span> and then pick the <span class="math-container">$k$</span> subrows of <span class="math-container">$a_{b_1}, \dots, a_{b_k}$</span> with maximum sum.</p>
<p>Both the factors of <span class="math-container">$k/n, 1/k$</span> are tight as demonstrated by the worst case. Thus, we have an algorithm which is good unless <span class="math-container">$k = o(n),$</span> and one which is good when <span class="math-container">$k = o(1).$</span> What do we do about the middle, when <span class="math-container">$k = \sqrt{n}$</span> for example?</p>

CC BY-SA 4.0
2023-07-28T14:49:24.613Z
I'm assuming the value $k$ is also part of the input?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-07-29T15:55:39.693Z
@a3nm That's correct.
Display name
<ds.algorithms><approximation-algorithms>
Finding $k \times k$ rectangle in a matrix with maximum sum
Display name
# Finding $k \times k$ rectangle in a matrix with maximum sum

(Asked by: username_0 on 2023-07-23)

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](https://web.math.princeton.edu/%7Enaor/homepage%20files/cutnorm.pdf) 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?

**Tags:** ds.algorithms, approximation-algorithms

> **Comments:**
> **username_1**: I'm assuming the value $k$ is also part of the input?  
> **username_0**: @a3nm That's correct.  

---

## 1 answers

### Answer by username_2 on 2023-08-05. Score: 3

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**](https://doi.org/10.1007/978-3-540-95995-3_3).

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](https://arxiv.org/abs/2303.14467) 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**](https://doi.org/10.1137/S0097539705447037)).


---

