Improved Approximation Algorithm for Maximum Balanced Biclique

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{\mathrm{\Omega }}((\log n{)}^3)}\right)$-approximation algorithm for the problem, which improves upon an $\left(\frac{n}{\mathrm{\Omega }((\log n{)}^2)}\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.