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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.