Matroids and the Greedy Algorithm.¶
Edmonds, J. (1971). Matroids and the Greedy Algorithm. Mathematical Programming, 1(1), 127-136.
Cited by¶
1 citation across 1 artifact.
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.
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:8d5ac8820657 · see in the full table