MetaVC -- A Meta Local Search Framework For Minimum Vertex Cover (MinVC)

MetaVC is a meta local search framework for minimum vertex cover (MinVC). MetaVC provides a top level design, where each key function is an abstraction and can be instantiated with a concrete function.

Author and Implementer

• Chuan Luo (chuan.luo@microsoft.com)

Reference

• Chuan Luo, Holger H. Hoos, Shaowei Cai, Qingwei Lin, Hongyu Zhang, Dongmei Zhang. Local Search with Efficient Automatic Configuration for Minimum Vertex Cover. In Proceedings of IJCAI 2019, pages 1297-1304, 2019.

LICENSE

• This project is licensed under the terms of the GPLv3 license.

Source Code of MetaVC

• The source code of MetaVC can be found in the directory entitled MetaVC_source_code.

Configuration Space, Default Configuration and Optimized Configurations of MetaVC and MetaVC2

• Everything can be found in the pdf file entitled MetaVC_configuration_details.pdf.
  • Table 1 reports the whole configuration space of MetaVC.
  • Table 2 reports the default configuration of MetaVC.
  • Table 3 reports the optimized configurations of MetaVC for all benchmarks.
  • Table 4 reports the optimized configurations of MetaVC2 for all benchmarks.

Benchmarks

• Details of benchmarks can be found in the pdf file entitled benchmarks_overview.pdf.

Experimental Results

• For experimental results on hard instances, the details can be found in the pdf file entitled Result_on_hard_benchmarks.pdf.

  • Table 1 reports the comparative results of MetaVC2, MetaVC, NuMVC, TwMVC and FastVC2+p on the DIMACS-HARD benchmark. (as the same as Table 1 in the submitted paper)
  • Table 2 reports the comparative results of MetaVC2, MetaVC, NuMVC, TwMVC and FastVC2+p on the BHOSLIB-HARD benchmark. (as the same as Table 2 in the submitted paper)
  • Table 3 reports the comparative results of MetaVC, NuMVC, TwMVC and FastVC2+p on the REAL-WORLD-HARD benchmark. (as the same as Table 3 in the submitted paper)
  • Table 4 reports the comparative results of MetaVC2, MetaVC and FastVC2+p on the REAL-WORLD-HARD benchmark. (as the same as Table 4 in the submitted paper)

• For experimental results on easy instances, the details can be found in the pdf file entitled Result_on_easy_benchmarks.pdf.

  • Table 1 reports the comparative results of MetaVC2, MetaVC, NuMVC, TwMVC and FastVC2+p on the DIMACS-EASY benchmark.
  • Table 2 reports the comparative results of MetaVC2, MetaVC, NuMVC, TwMVC and FastVC2+p on the BHOSLIB-EASY benchmark.
  • Tables 3 and 4 report the comparative results of MetaVC, NuMVC, TwMVC and FastVC2+p on the REAL-WORLD-EASY benchmark.
  • Tables 5 and 6 report the comparative results of MetaVC2, MetaVC, and FastVC2+p on the REAL-WORLD-EASY benchmark.