Improving Local Search for Minimum Weight Vertex Cover by Dynamic Strategies
Authors: Shaowei Cai, Wenying Hou, Jinkun Lin, Yuanjie Li
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this work, we evaluate the algorithms on the vertex weighted graphs that obtained from an important real world problem, the map labeling problem. Experiments show that our algorithm obtains better results than previous algorithms for MWVC and maximum weight independent set (MWIS) on these real world instances. We also test our algorithms on massive graphs studied in previous works, and show significant improvements there. |
| Researcher Affiliation | Academia | 1State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences 2School of Computer and Control Engineering, University of Chinese Academy of Sciences 3School of Information Technology and Management, University of International Business and Economics |
| Pseudocode | Yes | Algorithm 1: A Local Search Framework for MWVC; Algorithm 2: Dynamic Choose(no improve, α); Algorithm 3: Dyn WVC1 |
| Open Source Code | No | The paper provides a link (https://github.com/kit-algo/temporalmaplabeling) to the software used to generate conflict graphs for the map labeling benchmark, which was developed by Barth et al., not the open-source code for the Dyn WVC1 or Dyn WVC2 algorithms developed by the authors of this paper. |
| Open Datasets | Yes | We download the map files for North America from Open Street Map1 and generate conflict graphs from them using the software2 developed by Barth et al. [Barth et al., 2016], which are used as the benchmark. ... We also evaluate our algorithms on massive graphs from Network Data Repository [Rossi and Ahmed, 2015]. |
| Dataset Splits | No | The paper describes running algorithms multiple times and reporting average/best results, but does not provide specific train/validation/test dataset splits for model training and evaluation. |
| Hardware Specification | Yes | All experiments are run on a 4-way Intel Xeon E7-8850 v2 @ 2.30GHz CPU with 1TB RAM server under Cent OS 7.2. |
| Software Dependencies | No | The paper mentions that Dyn WVC1 and Dyn WVC2 are implemented in C++ and compiled by g++ with -O3 option, and run under Cent OS 7.2. However, it does not provide specific version numbers for the C++ compiler (g++) or any other key software libraries used. |
| Experiment Setup | Yes | The parameter in our algorithms α is set to 5. All algorithms are executed 10 times on each instance independently with a cutoff time of 1000 seconds. ... The weight of each vertex is assigned to a value from [20,100] uniformly at random. |