Premium
A parallel hybrid metaheuristic for bicluster editing
Author(s) -
Sousa Filho Gilberto F.,
Júnior Teobaldo L. Bulhões,
Cabral Lucídio dos Anjos F.,
Ochi Luiz Satoru,
Protti Fábio
Publication year - 2016
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12215
Subject(s) - metaheuristic , bipartite graph , computer science , grasp , vertex (graph theory) , graph , disjoint sets , local search (optimization) , algorithm , theoretical computer science , combinatorics , mathematics , programming language
Abstract The bicluster editing problem (BEP) consists of editing (adding or removing) the edges of a bipartite graph G in order to transform it into a vertex‐disjoint union of complete bipartite subgraphs, in such a way that the sum of the weights of the edited edges is minimum. In this paper, we propose five parallel strategies for the implementation of a hybrid metaheuristic for the BEP, consisting of a GRASP with VNS as local search. Computational experiments show near‐linear speedups on Linux cluster with 64 processors and better solutions than those of the sequential approach.