A Fast and Robust Heuristic Algorithm for the Minimum Weight Vertex Cover Problem
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
The minimum weight vertex cover problem (MWVCP) is a fundamental combinatorial optimization problem with various real-world applications. The MWVCP seeks a vertex cover of an undirected graph such that the sum of the weights of the selected vertices is as small as possible. In this paper, we present an effective algorithm to solve the MWVCP. First, a master-apprentice evolutionary algorithm based on two individuals is conducted to enhance the diversity of solutions. Second, a hybrid tabu search combined configuration checking and solution-based tabu search is introduced to intensify local search procedure. Harnessing the power of the evolutionary strategy and a novel variant of hybrid tabu search, Master-Apprentice Evolutionary Algorithm with Hybrid Tabu Search, MAE-HTS, is presented. Results of extensive computational experiments using standard benchmark instances and other large-scale instances demonstrate the efficacy of our algorithm in terms of solution quality, running time, and robustness compared to state-of-the-art heuristics from the literature and the commercial MIP solver Gurobi. We also systematically analyze the role of each individual component of the algorithm which when worked in unison produced superior outcomes. In particular, MAE-HTS produced improved solutions for 2 out of 126 public benchmark instances with better running time. In addition, our MAE-HTS outperforms other state-of-the-art algorithms DLSWCC and NuMWVC for 72 large scale MWVCP instances by obtaining the best results for 64 ones, while other two reference algorithms can only obtain 27 best results at most.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.000 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it