Greedy Algorithm¶
Core Idea¶
A greedy algorithm is the structural pattern of committing to the locally best available choice at each step, irrevocably, and continuing until the problem is solved. The defining commitment is no lookahead, no backtracking, no revision: at each decision point the strategy uses only the present local evaluation, and the choice is sealed. The pattern is interesting precisely because of its sharp success/failure dichotomy. 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.
The structural force comes from the same fact in every substrate: greedy is fast, simple, and parallel-friendly, but it pays an information cost, ignoring everything the local evaluation function cannot see. When the global optimum is a concatenation of locally optimal pieces (the matroid case), the cost is zero and greedy is unbeatable. When the global optimum requires a locally costly move to enable a later large gain — "give up cheese now for steak later" — greedy is structurally blind and systematically produces worse outcomes than even minimal lookahead. Naming a process as greedy makes this trade-off visible and selects the diagnostic question: is this problem matroid-shaped, and if not, where will greedy's blindness bite? The substrate-neutral skeleton is local commitment plus irrevocability plus the matroid criterion plus a small family of escape patches, and although the name is coined in computer science, the no-lookahead-no-backtrack commitment is a structural property that recurs in behaviour, evolution, policy, and learning.
How would you explain it like I'm…
Grab the Biggest Now
Best-Right-Now, No Takebacks
Local Best, No Lookahead
Structural Signature¶
a sequence of decision points — a local evaluation function scoring available choices — selection of the locally best choice — the irrevocability invariant (no lookahead, no backtracking) — the matroid criterion governing global optimality — the local-versus-global gap and its escape patches
A process is greedy when the following hold:
- A sequence of decision points. The problem is solved through a series of choices made one at a time until completion.
- A local evaluation function. At each point a score ranks the currently available choices using only present, local information — nothing about downstream consequences.
- Locally-best selection. The choice maximising the local score is taken at each step.
- Irrevocability. Each choice is sealed: no future step revises it, and no foresight informs it. This no-lookahead, no-backtrack commitment is what distinguishes greed from search, backtracking, or local-search- with-restart.
- The matroid criterion. Whether locally-best choices concatenate into a globally optimal solution is a structural property: if the feasible-set system has the matroid exchange property, greed is provably optimal; otherwise it is not.
- The local-versus-global gap. When the matroid property fails, a locally good choice can close a globally needed door; the failure is witnessed by a single counter-example and reparable by widening the local score, adding lookahead/backtracking, or adding randomisation/ restart.
These compose into one policy: evaluate locally, commit irrevocably to the best, repeat — fast and optimal on matroid-shaped problems, systematically suboptimal and trap-prone otherwise.
What It Is Not¶
- Not
dynamic_programming. Dynamic programming remembers and reuses subproblem solutions and chooses globally by combining them; greedy uses only present local evaluation with no memo table and no recombination of alternatives. DP buys optimality with bookkeeping; greedy forgoes both. - Not
local_optimum. A local optimum is a state property — a point no neighbouring move improves; greedy is a procedure that often lands in one. The trap is the outcome; greedy is the policy that walks into it. - Not
simulated_annealing. Annealing deliberately accepts locally worse moves (with cooling probability) to escape traps; greedy never accepts a locally worse move. Annealing is greedy's escape patch, defined by the opposite acceptance rule. - Not
heuristicin general. A heuristic is any rule-of-thumb shortcut; greedy is a specific heuristic schema — local-best, irrevocable, no-backtrack — with a sharp optimality theorem (matroids) most heuristics lack. - Not
satisficing. Satisficing stops at the first good-enough option against an aspiration threshold; greedy always takes the locally best available and continues to completion. One settles for adequate; the other optimizes locally at every step. - Common misclassification. Calling any fast approximate method "greedy." Catch it by checking the three commitments: is each choice the locally best, irrevocable, and made with no lookahead? If the method revises, backtracks, or plans ahead, it is not greedy.
Broad Use¶
The skeleton recurs across substrates. In computer science it is minimum spanning trees (provably optimal by matroid structure), Huffman codes, Dijkstra's algorithm, interval scheduling, and greedy set cover (a logarithmic-factor approximation, not exact). In behavioural economics and psychology it is hyperbolic discounting, the marshmallow test, addiction dynamics, and present bias — a decision rule that takes the locally best immediate payoff and forfeits larger delayed ones. In foraging and evolution it is the marginal value theorem and incremental fitness optimisation that locks populations onto local fitness peaks — a structural-greedy outcome of natural selection without lookahead. In economics and policy it is short-term budget balancing that ignores long-term obligations and electoral-cycle policy that optimises myopically per term. In bureaucracies and triage it is queue-by-loudest-complaint and deal-with-the-closest-deadline — greedy rules on a local salience metric. In negotiation it is taking each round's best offer instead of structuring multi-round trade-offs. In machine learning it is greedy decision-tree induction, greedy feature selection, and greedy sequence decoding versus beam search. In each, the same commitment — local best, sealed, no revision — produces the same strengths and the same characteristic failures.
Clarity¶
Naming a process as a greedy algorithm makes the commitment-irrevocability of each step explicit, separating it from processes that look like greed but actually allow revision — backtracking search, gradient descent with restart, local search. It also makes the evaluation function (what counts as "locally best") a discrete object that can be inspected, criticised, and changed. Many failures attributed to "shortsightedness" are actually a wrong evaluation function rather than a wrong algorithmic structure: the rule was greedy, but with the right local score it would have been fine. Distinguishing "the local score is wrong" from "greedy is wrong for this problem shape" is the single biggest clarifying move the prime provides. The frame also clarifies that greedy is not a bug — for matroid-shaped problems it is provably optimal and far more efficient than search alternatives — so recognizing the problem class first is the prerequisite to deciding whether greed is appropriate. The clarifying force is to make the commitment pattern, the evaluation function, and the problem's matroid status all explicit and separately inspectable.
Manages Complexity¶
Greedy compresses the decision policy to a single locally evaluable function and dispenses with state. There is nothing to remember, no tree to explore, no plan to maintain; memory and runtime are minimal, and parallelism is natural when each decision is local. When the problem permits greed, the algorithmic complexity is dramatically lower than any search alternative. When greedy fails, the diagnosis is also compact: trace the local choices, find the point where a locally good choice closed a globally needed door, and then either widen the local score (the cheap fix), accept a lookahead or backtracking cost (the expensive fix), or restructure the problem to be matroid-shaped (the structural fix). The management payoff is that an entire combinatorial search collapses, where the structure permits, into a stateless sweep of local decisions — and where it does not, the failure is localizable to a single door-closing step and reparable by one of three named patches.
Abstract Reasoning¶
The prime offers a tight reasoning kit. The matroid criterion is a substrate-independent test: if the problem's feasible-set system has the exchange property, greedy is globally optimal; otherwise it is not — the same theorem underwriting Kruskal's MST, certain optimal scheduling rules, and certain economic choice rules. The approximation ratio is the second handle: greedy set cover achieves a logarithmic factor, and that bound holds across substrates with the same structure (advertising audience selection, sensor placement, material coverage). The local-versus-global gap is diagnosed by one move — exhibit a single case where giving up a locally best choice enables a strictly better global outcome — the canonical counter-example shape across all greedy failures, from hyperbolic discounting to mortgaging the future for a quarter's earnings. And composition with randomisation or restart is a generic upgrade: greedy with random restart escapes local optima, and recognizing "add randomness to escape local optima" as a portable patch is itself an insight. The reasoner asks, of any sequential decision rule: is it committing locally, is the problem matroid-shaped, and if not, where does the blindness bite and which patch fixes it?
Knowledge Transfer¶
The intervention catalog transfers across substrates with no adjustment, and the failure modes carry explanatory power between domains. The matroid criterion explains why some pursuits are well-served by following local preferences (matroid-shaped goals like accumulating independent course credits) and others demand foresight (non-decomposable thresholds like saving for a down payment) — the same diagnostic in algorithms and in life. Natural selection is structurally greedy on fitness, and populations stay stuck on local peaks until drift, mutation, or environmental change supplies the randomisation a greedy process needs to escape — the same fact appearing in the cultural evolution of norms. Electoral cycles constrain policy to greedy on visible-now benefits, and the same upgrade patterns apply: lookahead as multi-year treaty commitments, randomisation as independent agencies, restart as constitutional moments. Behavioural patches for human myopia — commitment devices, defaults, savings auto-escalators — inspire algorithmic patches, constraints that prevent greedy from closing certain doors. The set-cover bound "within a logarithmic factor of optimal" ports verbatim to media buying and feature selection. The role mappings are direct: decision sequence ↔ choice points / time steps / life stages, local evaluation ↔ immediate gain / immediate payoff / quarterly earnings / information gain, irrevocability ↔ sealed move / sunk action / past commitment, matroid criterion ↔ does local-best concatenate to global-best, escape mechanisms ↔ lookahead / randomisation / restart. A practitioner who diagnoses a salesperson's call list as greedy-suboptimal — large accounts require multi-touch sequences the per-step rule undervalues — applies the same three-part fix (change the score, add lookahead, add restart) that patches a greedy investment policy, a greedy attention allocation, and a greedy diet rule. Because the commitment structure is substrate-free, the transfer is recognition of one shape across computation, behaviour, evolution, and policy, and the counter-example that exposes its failure has the same form everywhere.
Examples¶
Formal/abstract¶
Contrast Kruskal's minimum-spanning-tree algorithm (greedy succeeds) with greedy set cover (greedy approximates) as two worked instances that together expose the matroid criterion. In Kruskal's, the sequence of decision points is "consider edges in increasing weight order"; the local evaluation function scores each edge by its weight; the locally-best selection adds the cheapest edge that does not form a cycle; the choice is irrevocable — once added, an edge is never removed. The decisive fact is the matroid criterion: the forests of a graph form a matroid (the exchange property holds — any independent set can be augmented from a larger one), and the foundational theorem of greedy optimization guarantees that greedy on a matroid yields the global optimum. So Kruskal's greedy produces a provably minimal spanning tree, with zero gap between local and global, at far lower cost than any search. Greedy set cover shows the other regime: the items are sets, the local score is "cover the most still-uncovered elements," and the choice is sealed. Here the feasible-set system is not a matroid, so the local-versus-global gap opens — greedy can be forced into a solution a logarithmic factor worse than optimal, and the bound is tight, witnessed by a constructible counter-example where an early locally-best set forecloses a cheaper global cover. The intervention the prime enables: before deploying greed, test the matroid property — if it holds, greed is optimal and search is wasted effort; if not, expect (and bound) the suboptimality.
Mapped back: Kruskal's and set cover instantiate both faces of the prime — local-best irrevocable selection — with the matroid criterion deciding whether the local-global gap is zero (MST) or provably positive (set cover), exactly the structural test the prime makes central.
Applied/industry¶
Consider hyperbolic discounting in human choice and electoral-cycle policy as two applied instances of structural greed. In the marshmallow-test setting the decision sequence is successive moments of temptation; the local evaluation function scores the immediate payoff (eat the marshmallow now); the locally-best selection takes the present reward; and the choice is irrevocable — the eaten treat cannot be un-eaten. This is greedy on immediate gain, and its local-versus-global gap is the signature "give up a small reward now to enable a larger one later" that greed is structurally blind to. The prime's diagnosis distinguishes two failures: if the goal is matroid-shaped (accumulating independent course credits, where each local best concatenates), greed is fine; if it is a non-decomposable threshold (saving a full down payment, where partial progress unspent yields nothing), greed systematically fails — and the fix is one of the named escape patches: a commitment device (auto-escalating savings) is the behavioral analog of constraining the algorithm so it cannot close the needed door. Electoral-cycle policy runs the same structure at institutional scale: each term's local evaluation scores visible-now benefits, choices are sealed by the time horizon, and long-term obligations are forfeited exactly as a greedy algorithm forfeits delayed gains. The same three patches port: lookahead as multi-year treaty commitments, randomization as independent agencies insulated from the cycle, restart as constitutional moments. A salesperson's call list, greedily sorted by smallest immediate effort, fails the same way when large accounts need multi-touch sequences — and the same three-part fix applies.
Mapped back: Discounting and electoral myopia both run the prime end-to-end — local-best, irrevocable, no-lookahead choice — with the matroid status deciding whether the myopia is harmless, and the same lookahead/randomization/restart patches repairing it across psychology and policy.
Structural Tensions¶
T1 — Local Best versus Global Best. Greedy commits to the locally best choice with no lookahead; whether that concatenates into the global optimum is governed by the matroid criterion. The tension is scalar: on matroid-shaped problems the local-global gap is exactly zero, but off them a locally good move can close a globally needed door. The failure mode is deploying greed on a non-matroid problem and getting systematically suboptimal results — mortgaging a later large gain for an immediate small one. Diagnostic: test the exchange property; if it fails, exhibit the single counter-example where giving up a local best enables a strictly better global outcome.
T2 — Speed versus Information. Greed is fast, stateless, and parallel-friendly precisely because it ignores everything the local evaluation cannot see; that economy is bought with an information cost. The tension is between cheapness and foresight. The failure mode is choosing greed for its efficiency on a problem where the discarded downstream information was decisive, then paying in solution quality far more than the saved compute was worth. Diagnostic: ask what the local score cannot see, and whether that hidden information ever changes which choice is correct; if it does, the speed is a false economy.
T3 — Wrong Score versus Wrong Structure. A greedy failure has two distinct causes that look identical: the local evaluation function is wrong, or greed is wrong for this problem shape. The tension is diagnostic — the same bad outcome can mean "fix the score" or "abandon greed." The failure mode is the costly misattribution: rebuilding the algorithm to add lookahead when a corrected local score would have sufficed, or endlessly tuning the score on a problem that is structurally non-matroid and will never yield to greed. Diagnostic: ask whether some local score makes greed optimal here; if yes the score is the bug, if no the structure is.
T4 — Irrevocability versus Revision. The no-backtrack commitment is what distinguishes greed from search, backtracking, and local-search-with-restart; it is also what traps it in local optima. The tension is that sealing each choice buys statelessness but forfeits escape. The failure mode is mistaking a revisable process for greedy (or vice versa) — calling gradient-descent-with-restart "greedy" and missing that its restarts already escape the traps, or running true greed where the problem demanded the ability to undo. Diagnostic: ask whether any later step can revise an earlier choice; only a genuinely sealed sequence is greedy and subject to the local-optimum trap.
T5 — Exact Optimality versus Bounded Approximation. On some non-matroid problems (set cover) greed is not optimal but carries a provable approximation ratio — within a logarithmic factor; on others it can be arbitrarily bad. The tension is measurement: "greedy fails" hides a spectrum from a tight, trustworthy bound to unbounded loss. The failure mode is treating all greedy suboptimality as equivalent — either rejecting a greedy method that comes with a strong guarantee, or trusting one that has no bound at all. Diagnostic: ask whether the problem admits a known approximation ratio for greed; a bounded ratio licenses use, its absence forbids it.
T6 — Escape Patch versus Structural Fix. When greed fails, three patches differ in cost and permanence: widen the local score (cheap), add lookahead or backtracking (expensive), or restructure the problem to be matroid-shaped (structural). The tension is that the convenient patch is rarely the durable one. The failure mode is reaching for randomization or restart to paper over a problem whose structure should have been changed — adding noise to escape a local optimum that a reformulation would have eliminated, paying the escape cost on every run forever. Diagnostic: ask whether the problem can be made matroid-shaped before settling for a per-run escape mechanism.
Structural–Framed Character¶
Greedy Algorithm sits at the structural end of the structural–framed spectrum, aggregate 0.2: the defining commitment — take the locally best choice, seal it, never look ahead or backtrack — is a substrate-neutral relational property, and only two diagnostics carry any weight, both at the half-mark.
Vocabulary travels (0.5): the prime's name and sharpest theory — the matroid criterion, approximation ratios, Kruskal and set cover — are computer-science coinages, and that residual algorithmic flavour earns the half-point. But it is only half, because the bare commitment "local-best, irrevocable, no-lookahead" is stated without any CS lexicon and is read off natural processes directly: hyperbolic discounting in human choice, fitness optimization in evolution, electoral-cycle myopia in policy, foraging under the marginal value theorem — each instance tells the pattern in its own words. Institutional origin (0.5): the construct is named inside the algorithms discipline, so invoking it carries a faint disciplinary origin; yet the no-lookahead-no-backtrack shape genuinely exists in evolution and behaviour independent of any institution, which is why this is 0.5 rather than 1.0. The other three read zero. Evaluative weight (0): greed is not pejorative here — on matroid-shaped problems it is provably optimal, so the pattern is value-neutral until you specify the problem. Not human-practice-bound (0): natural selection is structurally greedy on fitness with no human practice whatsoever, the clearest possible demonstration that the pattern runs in a biological substrate indifferently. Recognized, not imported (0): to call a process greedy is to recognize a commitment structure already present — the local-versus-global gap and its single counter-example are read off the dynamics, not overlaid. Two half-points against three zeros land exactly at the 0.2 aggregate and structural label.
Substrate Independence¶
Greedy Algorithm is a strongly substrate-independent prime — composite 4 / 5 on the substrate-independence scale. The defining commitment — take the locally best available choice, seal it irrevocably, no lookahead and no backtracking — is a substrate-neutral relational property, which is why the structural abstraction sits high: the bare shape is stated without any computer-science lexicon and read off natural processes directly. Its domain breadth is wide and genuinely cross-kind: it appears as minimum spanning trees, Huffman codes, and greedy set cover in computer science; as hyperbolic discounting and the marshmallow test in behavioral economics; as the marginal value theorem and incremental fitness optimization in foraging and evolution; as electoral-cycle myopia in policy; and as greedy decision-tree induction and sequence decoding in machine learning. The transfer evidence is strong and unusually load-bearing because the failure mode itself carries explanatory power across substrates: the matroid criterion explains in one stroke why some pursuits are well served by following local preferences and others demand foresight, and the single counter-example "give up a local best to enable a larger global gain" has the identical form in algorithms, human myopia, evolutionary local peaks, and short-termist policy, with the same three escape patches (widen the score, add lookahead, add randomization/restart) porting verbatim. Natural selection being structurally greedy on fitness with no human practice confirms the pattern runs in a biological substrate indifferently. What caps it at 4 is a faint algorithmic accent: the name and sharpest theory — matroids, approximation ratios, Kruskal, set cover — are CS coinages that travel with the prime. Maximal-leaning abstraction, wide spread, and explanatory cross-domain transfer with a light CS accent give a confident 4.
- Composite substrate independence — 4 / 5
- Domain breadth — 4 / 5
- Structural abstraction — 4 / 5
- Transfer evidence — 4 / 5
Relationships to Other Primes¶
Parents (1) — more general patterns this builds on
-
Greedy Algorithm is a kind of Heuristic
The file: 'Not heuristic in general — greedy is a SPECIFIC heuristic schema (local-best, irrevocable, no-backtrack) with a sharp optimality theorem (matroids) most heuristics lack.' A specialization of heuristic.
Path to root: Greedy Algorithm → Heuristic → Trade-offs → Constraint
Neighborhood in Abstraction Space¶
Greedy Algorithm sits in a moderately populated region (56th percentile for distinctiveness): it has near-neighbors but no dense thicket of synonyms.
Family — Optimization & Constrained Search (18 primes)
Nearest neighbors
- Backtracking — 0.72
- Local Optimum — 0.72
- Markov Decision Processes (MDPs) — 0.71
- No Free Lunch Theorem — 0.71
- Premature Optimization — 0.70
Computed from structural-signature embeddings · 2026-06-14
Not to Be Confused With¶
The most important contrast is with dynamic_programming, its direct
algorithmic rival on the same class of problems. Both build a solution
incrementally, but they differ in what they remember and combine. A
greedy algorithm makes one locally-best choice at each step, commits to it
irrevocably, and never reconsiders — it keeps no record of the alternatives
not taken. Dynamic programming solves and stores the optimal answer to
every relevant subproblem and combines those stored answers, so it can
discover that a locally-suboptimal early move enables a globally-optimal
whole. This is exactly why DP is correct on problems with overlapping
subproblems and optimal substructure where greedy fails: DP pays in memory
and time to keep its options, greedy pays in suboptimality to stay fast. The
deep fact uniting them is that greedy is the special case that becomes
correct precisely when the problem has matroid structure — when local-best
choices compose into global-best without any need to revisit. A practitioner
who reaches for greedy on a problem that lacks the exchange property gets a
fast wrong answer; one who reaches for DP where greedy would suffice pays an
unnecessary memory cost.
It is also distinct from local_optimum, with which it is intimately but
asymmetrically related. A local optimum is a state: a configuration that no
single neighbouring move improves. A greedy algorithm is a process: a
policy of always taking the locally-best step. The connection is that greedy,
by never accepting a worse move, characteristically terminates at a local
optimum — but the two are different kinds of thing. The local optimum is the
landscape feature; greedy is the walker that gets stuck on it. Conflating
them obscures the remedy: you fix a greedy failure by changing the policy
(add lookahead, randomize, reformulate), whereas you describe a local
optimum by analysing the landscape. One is a thing to escape; the other is a
way of getting trapped.
A third confusion worth dissolving is with satisficing. Both are
"good-enough fast" strategies that forgo global optimization, but their
stopping logic is opposite. Satisficing scans options and stops at the first
that clears an aspiration threshold — it accepts the first adequate
candidate and asks no more. Greedy does not settle for adequate; at every
step it takes the locally best available option and keeps going until the
whole problem is solved. Satisficing is threshold-driven and may stop early
with a mediocre-but-acceptable result; greedy is maximization-driven at the
local level and runs to completion. Mistaking one for the other misreads the
behaviour — expecting a greedy method to halt at "good enough," or expecting
a satisficer to locally optimize every step.
For a practitioner the through-line is that greedy is a precise commitment — local-best, irrevocable, no-lookahead — and each neighbour relaxes a different clause: DP restores lookahead-via-memory, satisficing relaxes "best" to "good enough," and a local optimum is simply where the greedy commitment characteristically deposits you. Knowing which clause is in play tells you which tool, and which fix, the situation actually calls for.
Solution Archetypes¶
No catalogued solution archetypes reference this prime yet.