An Approximate Solution to the Minimum Vertex Cover Problem: The Salvador Algorithm
Minimum Vertex Cover has a classical linear-time ratio of $2$, and under the Unique Games Conjecture no polynomial-time algorithm achieves a fixed ratio below $2$ unless $\mathrm{P}=\mathrm{NP}$. We present version 0.1.4 of \textsc{Salvador}, a linear-time ensemble of seventeen strategies, numbered in the order in which they are computed: twelve base strategies (component amplification before a maximal matching, the maximal matching itself, degree and weight heuristics, reductions to auxiliary problems that are solved exactly, a decomposition into bipartite layers, a weighted subdivision…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00337
curl -X POST /api/v1/records/hexagon/2610.00337/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00337/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'