5
$\begingroup$

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?

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.