Improved Approximation Algorithm for Maximum Balanced Biclique

Abstract

We study the Maximum Balanced Biclique (MBB) problem: Given a bipartite graph $G$ with $n$ vertices on each side, find a balanced biclique in $G$ with maximum size. We give a polynomial-time $\left(\frac{n}{\tilde{\Omega }\left((\log n{)}^3\right)}\right)$-approximation algorithm for the problem, which improves upon an $\left(\frac{n}{\Omega \left((\log n{)}^2\right)}\right)$-approximation by Chalermsook et al. (2020) and answers their open question. Furthermore, our approximation ratio matches that of the maximum clique problem by Feige (2004) up to an $O(\log \log n)$ factor.