2017/05/20 by Yi Zhou, Zhou, Yi, André Rossi +3
Computer Science · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1705.07338
openalex publication_date 2017/05/20 · openalex created_date 2017/06/05 · openalex updated_date 2026/07/28
The Maximum Balanced Biclique Problem (MBBP) is a prominent model with numerous applications. Yet, the problem is NP-hard and thus computationally challenging. We propose novel ideas for designing effective exact algorithms for MBBP. Firstly, we introduce an Upper Bound Propagation procedure to pre-compute an upper bound involving each vertex. Then we extend an existing branch-and-bound algorithm by integrating the pre-computed upper bounds. We also present a set of new valid inequalities induced from the upper bounds to tighten an existing mathematical formulation for MBBP. Lastly, we investigate another exact algorithm scheme which enumerates a subset of balanced bicliques based on our upper bounds. Experiments show that compared to existing approaches, the proposed algorithms and formulations are more efficient in solving a set of random graphs and large real-life instances.