Resumen
The Maximum Balanced Biclique Problem (MBBP) consists of identifying a complete bipartite graph, or biclique, of maximum size within an input bipartite graph. This combinatorial optimization problem is solvable in polynomial time when the balance constraint is removed. However, it becomes NP –hard when the induced subgraph is required to have the same number of vertices in each layer. Biclique graphs have been proven to be useful in several real-life applications, most of them in the field of biology, and the MBBP in particular can be applied in the design of programmable logic arrays or nanoelectronic systems. Most of the approaches found in literature for this problem are heuristic algorithms based on the idea of removing vertices from the input graph until a feasible solution is obtained; and more recently in the state of the art an evolutionary algorithm (MA/SM) has been proposed. As stated in previous works it is difficult to propose an effective local search method for this problem. Therefore, we propose the use of Reduced Variable Neighborhood Search (RVNS). This methodology is based on a random exploration of the considered neighborhoods and it does not require a local search.
Jesús Sánchez-Oro
Profesor Titular de Universidad
Profesor Titular del Departamento de Informática, siendo uno de los investigadores principales del Grupo de Investigación de Algoritmos para la Optimización GRAFO.
Abraham Duarte
Catedrático de Universidad
Mi carrera investigadora se ha centrado en el desarrollo de nuevos algoritmos y técnicas de Inteligencia Computacional (metaheurísticas) y su aplicación a diferentes problemas en Ciencia e Ingeniería desde que me incorporé a la Universidad Rey Juan Carlos (URJC) en el octubre del año 2000.