Matroids and the Greedy Algorithm.¶
Edmonds, J. (1971). Matroids and the Greedy Algorithm. Mathematical Programming, 1(1), 127-136.
Cited by¶
3 citations across 3 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Greedy Algorithm
- For some problem structures — those satisfying a matroid or matroid-like exchange property — greedy choice is provably globally optimal; for others it is provably suboptimal and locks the search into local optima from which only foresight, randomisation, or restart can escape.
This sourceProves the foundational optimality theorem: the greedy algorithm yields a globally optimal solution exactly when the feasible-set system is a matroid (the exchange property holds), as for the forests of a graph underlying Kruskal's MST.
- For some problem structures — those satisfying a matroid or matroid-like exchange property — greedy choice is provably globally optimal; for others it is provably suboptimal and locks the search into local optima from which only foresight, randomisation, or restart can escape.
Mechanisms¶
- Kruskal-Style Edge Acceptance
- Its strength is that on a matroid the cheapest-legal rule is exactly optimal — a rare greedy that needs no approximation caveat — and the guard makes each acceptance auditable: every element is in the record because it connected something genuinely new.
This sourceProves that the greedy cheapest-legal selection rule is exactly optimal for weighted matroids.
- Its strength is that on a matroid the cheapest-legal rule is exactly optimal — a rare greedy that needs no approximation caveat — and the guard makes each acceptance auditable: every element is in the record because it connected something genuinely new.
- Sorted Candidate Sweep
- Its strength is extreme economy: one sort dominates the cost, the sweep is a single linear pass, and when the feasible sets form a matroid the frozen-order sweep is not just fast but exactly optimal
This sourceShows that an ordered greedy scan is a single pass and is exactly optimal for weighted matroids.
- Its strength is extreme economy: one sort dominates the cost, the sweep is a single linear pass, and when the feasible sets form a matroid the frozen-order sweep is not just fast but exactly optimal
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Not recorded. Neither this nor any other of the 3 citations of this work carries a recorded support check.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:8d5ac8820657 · see in the full table