NuMVC: an efficient local search algorithm for minimum vertex cover
From MaRDI portal
Abstract: The Minimum Vertex Cover (MVC) problem is a prominent NP-hard combinatorial optimization problem of great importance in both theory and application. Local search has proved successful for this problem. However, there are two main drawbacks in state-of-the-art MVC local search algorithms. First, they select a pair of vertices to exchange simultaneously, which is time-consuming. Secondly, although using edge weighting techniques to diversify the search, these algorithms lack mechanisms for decreasing the weights. To address these issues, we propose two new strategies: two-stage exchange and edge weighting with forgetting. The two-stage exchange strategy selects two vertices to exchange separately and performs the exchange in two stages. The strategy of edge weighting with forgetting not only increases weights of uncovered edges, but also decreases some weights for each edge periodically. These two strategies are used in designing a new MVC local search algorithm, which is referred to as NuMVC. We conduct extensive experimental studies on the standard benchmarks, namely DIMACS and BHOSLIB. The experiment comparing NuMVC with state-of-the-art heuristic algorithms show that NuMVC is at least competitive with the nearest competitor namely PLS on the DIMACS benchmark, and clearly dominates all competitors on the BHOSLIB benchmark. Also, experimental results indicate that NuMVC finds an optimal solution much faster than the current best exact algorithm for Maximum Clique on random instances as well as some structured ones. Moreover, we study the effectiveness of the two strategies and the run-time behaviour through experimental analysis.
Recommendations
- Local search with edge weighting and configuration checking heuristics for minimum vertex cover
- Combining edge weight and vertex weight for minimum vertex cover problem
- An efficient local search framework for the minimum weighted vertex cover problem
- Towards faster local search for minimum weight vertex cover on massive graphs
- scientific article; zbMATH DE number 6303718
Cited in
(33)- A warning propagation-based linear-time-and-space algorithm for the minimum vertex cover problem on giant graphs
- An efficient heuristic algorithm for solving connected vertex cover problem
- NuMVC
- An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network
- An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
- Towards faster local search for minimum weight vertex cover on massive graphs
- \(\boldsymbol{borealis}\) -- a generalized global update algorithm for Boolean optimization problems
- An improved configuration checking-based algorithm for the unicost set covering problem
- An efficient local search framework for the minimum weighted vertex cover problem
- SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem
- Backdoors to tractable answer set programming
- Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism
- Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs
- Can local optimality be used for efficient data reduction?
- Combining edge weight and vertex weight for minimum vertex cover problem
- Local search for Boolean satisfiability with configuration checking and subscore
- CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability
- Finding a small vertex cover in massive sparse graphs: construct, local search, and preprocess
- scientific article; zbMATH DE number 6303718 (Why is no real title available?)
- An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem†
- A vertex weighting-based double-tabu search algorithm for the classical p-center problem
- Dual-neighborhood iterated local search for routing and wavelength assignment
- An efficient local search algorithm for minimum positive influence dominating set problem
- Local search with edge weighting and configuration checking heuristics for minimum vertex cover
- PACE solver description: mount doom -- an exact solver for directed feedback vertex set
- PACE solver description: diverses -- a heuristic solver for the directed feedback vertex set problem
- The PACE 2022 parameterized algorithms and computational experiments challenge: directed feedback vertex set
- Parameterized local search for vertex cover: when only the search radius is crucial
- Finding 3-swap-optimal independent sets and dominating sets is hard
- Supervised Gromov-Wasserstein optimal transport with metric-preserving constraints
- Can local optimality be used for efficient data reduction?
- Hostile, compatible, or free: a constant time classification of pairwise shortest path conflicts in obstacle-free MAPF
- Fantastic flips and where to find them: a general framework for parameterized local search on partitioning problems
This page was built for publication: NuMVC: an efficient local search algorithm for minimum vertex cover
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4917618)
