Two Weighting Local Search for Minimum Vertex Cover
Authors: Shaowei Cai, Jinkun Lin, Kaile Su
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments show that Tw MVC outperforms Nu MVC on the standard benchmarks namely DIMACS and BHOSLIB. To the best of our knowledge, Tw MVC is the first Min VC algorithm that attains the best known solution for all instances in both benchmarks. |
| Researcher Affiliation | Academia | 1State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China 2Key Laboratory of High Confidence Software Technologies, Peking University, Beijing, China 3Institute for Integrated and Intelligent Systems, Griffith University, Brisbane, Australia |
| Pseudocode | Yes | Algorithm 1: A Local Search Framework of Min VC; Algorithm 2: Tw MVC; Algorithm 3: choose Add V ertex(e) |
| Open Source Code | Yes | Tw MVC is programmed in C++, on the basis of source codes of Nu MVC6. Available from http://lcs.ios.ac.cn/~caisw/MVC.html |
| Open Datasets | Yes | The DIMACS benchmark is taken from the Second DIMACS Implementation Challenge for the Maximum Clique problem (1992-1993)3... The BHOSLIB4 (Benchmarks with Hidden Optimum Solutions) instances were generated in the phase transition area according to model RB (Xu et al. 2007)... The web link networks5 were generated from web pages online. |
| Dataset Splits | No | The paper does not specify training/test/validation dataset splits, as it concerns combinatorial optimization algorithms evaluated on entire benchmark instances rather than machine learning models trained on split data. |
| Hardware Specification | Yes | All experiments are carried out on a machine under Linux, using an Intel(R) Core(TM) 2.8 GHz CPU and 4 GB RAM. |
| Software Dependencies | Yes | Both algorithms are complied by g++ (version 4.4.5) with the -O2 option. |
| Experiment Setup | Yes | The parameters in Tw MVC are tuned manually based on experiments, and are set as follows. Setting β and δ: ... For all instances: β = 0.8 and δ = 100000. Setting γ: ... Finally, γ is set to |E|/7 for most instances, except for C instances (where γ = |E|/15), MANN instances (where γ = |E|/3.3) and web instances (where γ = |E|/10). Although the above setting can already yield good performance on brock instances, we observe a much better setting for brock instances is: β = 1, delta = 10000 and γ = 1500, which is adopted in our experiment. |