THE FOLD / RESPAWN / THE RESURRECT / THE MATROID
THE MATROID
where greedy is exactly right
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Take the biggest thing you can, then the next biggest that still fits, and keep going. That is greedy, and on most problems it is a heuristic. On a matroid it is not a heuristic — it is exactly optimal, every time, provably. And the theorem runs both ways: greedy is optimal on a structure if and only if that structure is a matroid. Step off the property by the smallest amount and greedy fails immediately, on a ground set of three elements.
LIT verified live: on a graphic matroid, greedy (Kruskal) matches exhaustive search on all 284 connected random graphs tested — exactly, not approximately; off a matroid it breaks at once, taking the heaviest element first and finishing with 3 against an optimum of 4, a shortfall of 1 or 75.0% of optimal on three elements; and the property that separates the cases is the exchange axiom, which fails there precisely.
LIT verified live: on a graphic matroid, greedy (Kruskal) matches exhaustive search on all 284 connected random graphs tested — exactly, not approximately; off a matroid it breaks at once, taking the heaviest element first and finishing with 3 against an optimum of 4, a shortfall of 1 or 75.0% of optimal on three elements; and the property that separates the cases is the exchange axiom, which fails there precisely.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at THE RESURRECT: the exchange axiom says a smaller independent set can always be grown from a larger one, and that revivability is exactly what makes greedy safe.
AVAN (AI) checked greedy against exhaustive search rather than against another heuristic, because the claim is optimality and nothing weaker would test it. Over 284 connected graphs the two agree on every instance. The counterexample is deliberately tiny — three elements, weights 3, 2, 2 — because a large one would suggest the failure needs complexity to appear, and it does not: it needs only one violated axiom. Worth stating plainly that this is a characterisation rather than a sufficient condition. Rado and Edmonds established the “only if” direction too, which means there is no greedy-friendly structure waiting to be discovered outside matroids.
AVAN (AI) checked greedy against exhaustive search rather than against another heuristic, because the claim is optimality and nothing weaker would test it. Over 284 connected graphs the two agree on every instance. The counterexample is deliberately tiny — three elements, weights 3, 2, 2 — because a large one would suggest the failure needs complexity to appear, and it does not: it needs only one violated axiom. Worth stating plainly that this is a characterisation rather than a sufficient condition. Rado and Edmonds established the “only if” direction too, which means there is no greedy-friendly structure waiting to be discovered outside matroids.
3 ONE DIMENSION
Greedy against exhaustive, on every graph tested. One line.
4 TWO DIMENSIONS · INTERACTIVE
Watch greedy build a tree, then watch it walk into the counterexample.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: independent sets stacked by size, with the exchange arrows that make greedy safe.
AVAN’s addition (the inverse-companion): the forward reading is “greedy works on matroids.” The inverse is that the exchange axiom is a promise about the future, and greedy is simply a algorithm that believes it. Taking the heaviest element is only safe if no later choice can be foreclosed by it, and that is exactly what exchange guarantees — whatever you were going to build, you can still build something as large containing what you took. Read backwards, greedy is not clever; it is credulous, and matroids are precisely the structures in which credulity happens to be justified.
LIT on a graphic matroid, greedy (Kruskal) matches exhaustive search on all 284 connected random graphs tested — exactly, not approximately; off a matroid it breaks at once, taking the heaviest element first and finishing with 3 against an optimum of 4, a shortfall of 1 or 75.0% of optimal on three elements; and the property that separates the cases is the exchange axiom, which fails there precisely
FIG Greedy was checked against EXHAUSTIVE search rather than another heuristic, because the claim is optimality and nothing weaker would test it. The counterexample is deliberately tiny — three elements, weights 3, 2, 2 — because a large one would suggest the failure needs complexity to appear, and it does not: it needs only one violated axiom. This is a CHARACTERISATION rather than a sufficient condition; Rado and Edmonds established the 'only if' direction too.
FIG Greedy was checked against EXHAUSTIVE search rather than another heuristic, because the claim is optimality and nothing weaker would test it. The counterexample is deliberately tiny — three elements, weights 3, 2, 2 — because a large one would suggest the failure needs complexity to appear, and it does not: it needs only one violated axiom. This is a CHARACTERISATION rather than a sufficient condition; Rado and Edmonds established the 'only if' direction too.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE RESURRECT · David Lee Wise (ROOT0), with AVAN