Local Search for Maximum Weight Clique Problem |
The maximum clique
problem (MCP) consists in finding a clique with maximum number of vertices.
An important generalization of MCP is the maximum weight clique problem
(MWCP), in which each vertex is associated with a non-negative integer, and
the goal is to find a clique with the largest total weight. |
Local search solvers for
MWCP |
I have developed two local
search solvers for MWCP. The executable files are available below. |
Strong configuration checking (SCC) is a new variant of a
recent powerful strategy called configuration checking (CC) for reducing
cycling in local search. Based on the SCC strategy, we develop a local search
algorithm named LSCC. |
A low-complexity heuristic called Best from Multiple
Selection (BMS) is used to select the swapping vertex pair quickly and
effectively on massive graphs. The BMS heuristic is used to improve LSCC,
resulting in the LSCC+BMS algorithm. |
---Reference: Wang Yiyuan, Cai Shaowei, & Yin
Minghao. Two Efficient Local Search Algorithms for Maximum Weight Clique
Problem. Proceedings of the Thirtieth AAAI Conference on Artificial
Intelligence, 2016, 805-811. |