Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Discrete Mathematics | Complete bipartite graph,Discrete mathematics,Combinatorics,Random graph,Vertex (geometry),Exact algorithm,Upper and lower bounds,Algorithm,Mathematics |
DocType | Volume | Citations |
Journal | abs/1705.07338 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yi Zhou | 1 | 230 | 32.97 |
| André Rossi | 2 | 3 | 0.81 |
| Jin-Kao Hao | 3 | 2744 | 191.49 |