Volume 55, 2021Regular articles published in advance of the transition of the journal to Subscribe to Open (S2O). Free supplement sponsored by the Fonds National pour la Science Ouverte
|Page(s)||S741 - S763|
|Published online||02 March 2021|
A BRKGA-based matheuristic for the maximum quasi-clique problem with an exact local search strategy
Instituto Federal de Educação, Ciência e Tecnologia do Triângulo Mineiro, Uberlândia, MG 38411-104, Brazil
2 Institute of Computing, Universidade Federal Fluminense, Niterói, RJ 24210-346, Brazil
* Corresponding author: firstname.lastname@example.org
Accepted: 4 January 2020
Given a graph G = (V, E) and a threshold γ ∈ (0, 1], the maximum cardinality quasi- clique problem consists in finding a maximum cardinality subset C* of the vertices in V such that the density of the graph induced in G by C* is greater than or equal to the threshold γ. This problem has a number of applications in data mining, e.g., in social networks or phone call graphs. We propose a matheuristic for solving the maximum cardinality quasi-clique problem, based on the hybridization of a biased random-key genetic algorithm (BRKGA) with an exact local search strategy. The newly proposed approach is compared with a pure biased random-key genetic algorithm, which was the best heuristic in the literature at the time of writing. Computational results show that the hybrid BRKGA outperforms the pure BRKGA.
Mathematics Subject Classification: 05C69 / 05C85 / 68T20 / 90C27 / 90C59
Key words: Maximum quasi-clique problem / maximum clique problem / biased random-key genetic algorithm / metaheuristics / matheuristics
© EDP Sciences, ROADEF, SMAI 2021
Initial download of the metrics may take a while.