×

A BRKGA-based matheuristic for the maximum quasi-clique problem with an exact local search strategy. (English) Zbl 1469.05135

Summary: Given a graph \(G = (V, E)\) and a threshold \(\gamma \in (0, 1]\), the maximum cardinality quasi- clique problem consists in finding a maximum cardinality subset \(C^\ast\) of the vertices in \(V\) such that the density of the graph induced in \(G\) by \(C^\ast\) is greater than or equal to the threshold \(\gamma \). 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.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C42 Density (toughness, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.