I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix:

    111000011100001101000001001111111111000
    111000011100001101000000101111111111000
    111111111111110010010100000011100000000
    000111100011111100110000001100011111010
    111111111111110010010010000011100000000
    111000011100001101000000011111111111000
    000111100011111100110000001100011111100
    111111111111110010011000000011100000000
    000111100011111100110000001100011111001

I want to find the maximum value of the product $(1+|C_1|)(1+|C_2|)$, where $C_1$ and $C_2$ are any two disjoint subsets of the column indexes of $A$, such that for every $i \in C_1$ and every $j \in C_2$ and for every $1 \le k \le m$, either $a_{ki} = 1$ or $a_{kj} =1 $. It is not required that $C_1 \cup C_2 = [n] = \{1, \ldots, n\}$.

For example, if we permute rows and columns of the above matrix we get:

    111111111111111111000000000100100000000
    111111111111111111000000000100010000000
    111111111111111111000000000100001000000
    111111111000000000111111111010000100000
    111111111000000000111111111010000010000
    111111111000000000111111111010000001000
    000000000111111111111111111001000000100
    000000000111111111111111111001000000010
    000000000111111111111111111001000000001

and then it is clear that $\max{(1+|C_1|)(1+|C_2|)} = 10 \cdot 20 = 200$.

The matrix $A$ can be regarded as the biadjency matrix of a bipartite graph and $C_1$ and $C_2$ correspond to two complete bipartite supgraphs such that the union of their respective "row" parts gives the "row" part of the bipartite graph corresponding to $A$.

I could try all possible choices for $C_1$ and then evaluate the product based on the $C_2$ that follows, but the algorithm has a time complexity greater than $O(2^n)$.

Can we do better than that? Is there any measure (e.g. some entropy measure) to at least estimate the maximum value?