Problem dossier · Algorithms & Simulation
Heuristics vs. exact methods on NP-hard problems
On specific graph families, how close do learned or AI-generated heuristics get to exact optima for max-cut, vertex cover, and TSP variants — and where exactly do they fail?
§1
Status
Open-ended benchmark frontier: moderate sizes where exact solvers still certify optima are the honest testing ground for heuristic claims.
Think you can crack this one? Read the playbook before you announce →
§2
The Angle of Attack
Build paired pipelines (exact ILP/branch-and-bound vs. generated heuristics) on structured families; log optimality gaps and failure structure; iterate the heuristics against their own failure cases.
Tags: max-cut · vertex cover · tsp · benchmarks · heuristics
§3
The Lab
No instruments built yet. When this problem gets tackled, its interactive instruments — explorers, searches, verifiers running in the browser — live here. See the Collatz dossier for what a fully tackled problem looks like.
§4
The Log
Empty. Work on this problem gets logged here as dated entries — constructions tried, code run, dead ends included. Dead ends are results.
§5
Related Problems
More open problems in Algorithms & Simulation and adjacent territory.
- Map folding & polyomino folding — Algorithms & Simulation
- Minimal superpermutations — extended search — Algorithms & Simulation
- Self-avoiding walks — Algorithms & Simulation
- Small hard CSP/SAT instances — Algorithms & Simulation
- Superpermutation problem — Combinatorics