Reactive Local Search for the Maximum Clique Problem

TitleReactive Local Search for the Maximum Clique Problem
Publication TypeTechnical Report
Year of Publication1995
AuthorsBattiti, R.., & Protasi M.
Other Numbers992
Keywordsheuristic algorithms, maximum clique problem, reactive search, tabu search

A new Reactive Local Search (RLS) algorithm is proposed for the solution of the Maximum-Clique problem. RLS is based on local search complemented by a feedback (memory-based) scheme to determine the amount of diversification. The reaction acts on the single parameter that decides the temporary prohibition of selected moves in the neighborhood, in a manner inspired by Tabu Search. The performance obtained in computational tests appears to be significantly better with respect to all algorithms tested at the the second DIMACS implementation challenge. The worst-case complexity per iteration of the algorithm is O(max{n,m}) where n and m are the number of nodes and edges of the graph. In practice, when a vertex is moved, the number of operations tends to be proportional to its number of missing edges and therefore the iterations are particularly fast in dense graphs.

Bibliographic Notes

ICSI Technical Report TR-95-052

Abbreviated Authors

R. Battiti and M. Protasi

ICSI Publication Type

Technical Report