The Esperanza Algorithm for Maximum Independent Set
The maximum independent set problem asks for the largest set of pairwise non-adjacent vertices in an undirected graph. It is NP-hard to approximate within $n^{1-\varepsilon}$ for every $\varepsilon>0$, and under the Unique Games Conjecture it is hard to approximate within $O(\Delta/\log^2\Delta)$ on graphs of maximum degree $\Delta$; the Khot--Regev form of the conjecture, for which a proof has been reported but not yet peer reviewed, also rules out a $(2-\varepsilon)$-approximation of Minimum Vertex Cover. We present version 0.1.6 of \textsc{Esperanza}, which takes the better of a dynamic…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00703
curl -X POST /api/v1/records/hexagon/2610.00703/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00703/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'