Research map / Learning theory and algorithms / Combinatorial and search optimization
Systematic Exploration of Larger Local Search Neighborhoods for the Minimum Vertex Cover Problem
Maximilian Katzmann, Christian Komusiewicz
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add pruning rules 1 and 2 to the k-swap search (ablation) | k-swap local search for Minimum Vertex Cover · large graphs | search space size | Improved |
| add pruning rules to the k-swap search (ablation) | k-swap local search for Minimum Vertex Cover · large graphs | running time | Improved |
| increase neighborhood radius k up to about 9 | hill climbing from greedy cover · large graphs | relative improvement over greedy cover: median approximately 5% for k >= 9 | Improved |
| start from greedy vertex cover instead of trivial cover (ablation) | k-swap hill climbing · benchmark graphs | k needed to reach optimum | Improved |
| post-process FastVC solution with k-swap search | FastVC · soc-delicious, tech-RL-caida, citationCiteseer | vertex cover size: improves by 4, 25, and 9 | Improved |
Closest papers by meaning
- Local Search with Dynamic-Threshold Configuration Checking and Incremental Neighborhood Updating for Maximum k-plex Problem (AAAI 2020 · similarity 0.88)
- The Query Complexity of Local Search in Rounds on General Graphs (NeurIPS 2026 · similarity 0.86)
- Towards a Theoretical Understanding of Why Local Search Works for Clustering with Fair-Center Representation (AAAI 2024 · similarity 0.85)
- Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover (AAAI 2024 · similarity 0.84)
- Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.84)
- Pre-Assignment Problem for Unique Minimum Vertex Cover on Bounded Clique-Width Graphs (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
