  The Maximum Balanced Biclique Problem is a well-known graph model with
relevant applications in diverse domains. This paper introduces a novel
algorithm, which combines an effective constraint-based tabu search procedure
and two dedicated graph reduction techniques. We verify the effectiveness of
the algorithm on 30 classical random benchmark graphs and 25 very large
real-life sparse graphs from the popular Koblenz Network Collection (KONECT).
The results show that the algorithm improves the best-known results (new lower
bounds) for 10 classical benchmarks and obtains the optimal solutions for 14
KONECT instances.
