Improved Approximation Algorithm for Maximum Balanced Biclique
For researchers in approximation algorithms, this provides a better theoretical guarantee for a fundamental graph problem, though the improvement is incremental.
The paper improves the approximation ratio for the Maximum Balanced Biclique problem from n/Ω((log n)^2) to n/Ω̃((log n)^3), matching the best known for maximum clique up to an O(log log n) factor.
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}{\widetildeΩ\left((\log n)^3\right)}\right)$-approximation algorithm for the problem, which improves upon an $\left(\frac{n}{Ω\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.