Two Efficient Local Search Algorithms for Maximum Weight Clique Problem
Authors: Yiyuan Wang, Shaowei Cai, Minghao Yin
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments show that the proposed algorithms outperform the state-of-the-art local search algorithm MN/TS and its improved version MN/TS+BMS on the standard benchmarks namely DIMACS and BHOSLIB, as well as a wide range of real world massive graphs. |
| Researcher Affiliation | Academia | 1School of Computer Science and Information Technology, Northeast Normal University, Changchun, China 2State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China 3Symbol Computation and Knowledge Engineer of Ministry of Education, Jilin University, Changchun, China |
| Pseudocode | Yes | Algorithm 1: LSCC (G, cutoff) |
| Open Source Code | No | The paper states that MN/TS is open-source, but there is no explicit statement or link indicating that the code for the authors' proposed methods (LSCC, LSCC+BMS) is publicly available. |
| Open Datasets | Yes | We carry out extensive experiments to evaluate the performance of the LSCC algorithm for MWCP on two standard benchmarks, including DIMACS and BHOSLIB. DIMACS benchmarks are from the Second DIMACS Implementation Challenge (Johnson and Trick 1996)... BHOSLIB instances are generated randomly based on the model RB at the phase transition area (Xu et al. 2005). |
| Dataset Splits | No | The paper describes experiments on benchmark instances and real-world graphs but does not specify any training, validation, or test dataset splits. The methodology focuses on finding maximum weight cliques within a given time limit, not on model training with partitioned data. |
| Hardware Specification | Yes | All the experiments were run on Ubuntu Linux, with 3.1 GHZ CPU and 8GB memory. |
| Software Dependencies | Yes | Our algorithm LSCC is also implemented in C++. Both of two algorithms are compiled by g++ 4.6.2 with the O2 option. |
| Experiment Setup | Yes | For the search depth L, MN/TS and LSCC set L=4000 for all instances. MN/TS employs a tabu heuristic and the tabu tenure TL is set to 7 as in (Wu, Hao, and Glover 2012)... For each instance, each algorithm is performed 100 independent runs with different random seeds, where each run is terminated upon reaching a given time limit (1000 seconds). For the BMS heuristic in both LSCC+BMS and MN/TS+BMS, we set the k parameter to 100, according to some preliminary experiments. |