Greedy Algorithms — Proof Techniques

A greedy algorithm makes a sequence of locally-optimal choices, each fixed once made, in the hope of arriving at a globally-optimal solution. The seductive simplicity of the approach hides a real difficulty: most greedies are wrong, and the ones that are right require a real proof of correctness. This note is the meta-reference for the two canonical proof techniques — exchange arguments and greedy stays ahead — plus the deep structural result (Edmonds 1971) that connects greedy optimality to matroids. The corollary the interviewer wants to see: a candidate who proposes a greedy must justify it, and a candidate who hasn’t internalized the failure modes (coin change with non-canonical denominations, vertex cover, the traveling salesman) will reach for greedy when dynamic programming is required.

1. Intuition — The Hiker’s Dilemma

Imagine a hiker descending a mountain at night with only a flashlight. At every step, the rational local policy is to step in whichever direction goes most steeply downward. On a smooth, convex valley this works perfectly: the locally-optimal path is also globally optimal — you reach the bottom by always going downhill. On a ridge with a saddle, however, the greedy hiker walks straight into a basin that is not the deepest one available, gets stuck on a local minimum, and never finds the true valley three ridges over.

This is the entire greedy story in one image. The problem’s structure decides whether greedy works. Some problems are “smooth valleys” — interval scheduling, minimum spanning tree, Huffman coding, fractional knapsack — where the local rule provably leads to a global optimum. Others have ridges and saddles — coin change with arbitrary denominations, vertex cover, the traveling salesman — where greedy gets stuck on a sub-optimum. The proof techniques in this note are the formal apparatus for distinguishing the two cases.

The mistake an interview candidate makes is reasoning in the opposite direction: “this looks like it could be greedy, let’s try it and see if it passes the tests.” That gets you partial credit at best. The senior signal is “this problem has property P, therefore a greedy works (or doesn’t), and here is the proof.”

2. Tiny Worked Example — The Coin Change Counterexample

Before the formal techniques, the single most useful interview vignette: a problem where greedy seems obviously right and is silently wrong.

Problem. Make change for amount n using denominations D = {d₁, d₂, …, d_k}, minimizing the number of coins. (See Coin Change for the dynamic-programming solution.)

Greedy proposal. Sort denominations descending. Repeatedly take the largest coin ≤ remaining amount.

Where greedy works. With “canonical” denomination sets — e.g., U.S. currency {1, 5, 10, 25} or {1, 2, 5, 10, 20, 50, 100, 200, 500} — the greedy is provably optimal. (Pearson 2005 gives a O(n³) algorithm to test whether a denomination system is canonical.)

Where greedy fails. Denominations D = {1, 3, 4}, target n = 6.

Greedy walk:
  remaining 6 → take 4 → remaining 2
  remaining 2 → no 4, no 3 → take 1 → remaining 1
  remaining 1 → take 1 → remaining 0
  Result: 4 + 1 + 1 = 3 coins.

Optimal:
  3 + 3 = 2 coins.

The greedy is off by 50%. This is the canonical “greedy fails” story to drop in any interview where someone reaches for greedy on a coin-change-shaped problem. The lesson: even when the local rule is natural and intuitive, you need a proof, because counterexamples exist for almost every greedy that isn’t on a matroid (see §6).

3. Pseudocode — The Generic Greedy Template

Most greedy algorithms fit this pattern:

greedy(problem):
    sort or order the input by some greedy key
    solution := empty
    for each candidate x in greedy order:
        if x is compatible with solution:
            solution.add(x)
    return solution

The two design choices are:

1. The greedy key — what ordering function ranks candidates.
2. Compatibility — what predicate decides whether a candidate can join the partial solution.

The proof obligation is to show that the chosen key + compatibility together yield a globally-optimal final solution. The two techniques in §5 and §6 are the standard tools.

4. Python Implementation — Greedy Skeleton + Coin Change Comparison

def greedy_skeleton(candidates, key, is_compatible):
    """Generic greedy: sort by key, scan, accept if compatible.
 
    Returns the constructed solution. Whether it's globally optimal
    depends on properties of `key` and `is_compatible` — see §5, §6.
    """
    solution = []
    for x in sorted(candidates, key=key):
        if is_compatible(x, solution):
            solution.append(x)
    return solution
 
 
def coin_change_greedy(denominations, target):
    """Naive greedy: largest coin first. CORRECT only for canonical denomination sets.
 
    Returns: number of coins, or None if no representation exists.
    """
    coins = 0
    for d in sorted(denominations, reverse=True):
        while target >= d:
            target -= d
            coins += 1
    return coins if target == 0 else None
 
 
def coin_change_dp(denominations, target):
    """[[Coin Change]] DP — correct for ANY denomination set.
 
    dp[i] = min coins to make amount i, or +inf if impossible.
    Recurrence: dp[i] = 1 + min(dp[i - d] for d in denominations if d <= i).
    """
    INF = float('inf')
    dp = [0] + [INF] * target
    for i in range(1, target + 1):
        for d in denominations:
            if d <= i and dp[i - d] + 1 < dp[i]:
                dp[i] = dp[i - d] + 1
    return dp[target] if dp[target] != INF else None
 
 
# The canonical disagreement
print(coin_change_greedy([1, 3, 4], 6))   # 3  (= 4 + 1 + 1, suboptimal)
print(coin_change_dp([1, 3, 4], 6))       # 2  (= 3 + 3, optimal)

The two functions disagree on the answer. That disagreement is the proof, in code form, that the greedy is wrong for this denomination set — a single counterexample is sufficient to refute optimality.

5. Technique 1 — The Exchange Argument

The exchange argument is the most common greedy-correctness proof. The structure:

1. Let G be the solution the greedy produces.
2. Let O be any optimal solution. (We do not pick a specific one — the proof must work for an arbitrary optimum.)
3. Show that O can be transformed step-by-step into G by a sequence of exchanges, each of which does not lose optimality (preserves objective value, or improves it).
4. Conclude that G is itself optimal.

The exchanges are typically of the form “swap an element of O for the corresponding greedy choice.” The proof obligation is that each such swap is safe.

5.1 Why this works

Each exchange produces a new solution that is (a) at least as good as the previous one, and (b) more “greedy-like” (one more position aligns with the greedy’s choice). After finitely many exchanges, we reach the greedy solution itself. The objective value never went down, so the greedy is at least as good as the optimum we started with — i.e., the greedy is optimal.

5.2 Worked example — Activity Selection

(Full proof in Activity Selection §5; the abbreviated version here.)

Setup. Let intervals be sorted by finish time. Let G = (g₁, …, g_k) be the greedy’s choices (in finish order), O = (o₁, …, o_m) be any optimal solution.

Inductive claim. For all i ≤ k, f_{g_i} ≤ f_{o_i} — the greedy’s i-th choice finishes no later than the optimum’s.

Base. g₁ is the earliest-finishing interval overall, so f_{g₁} ≤ f_{o₁} trivially.

Step. If f_{g_{i-1}} ≤ f_{o_{i-1}}, then at the moment the greedy picks g_i, the interval o_i is still available (since s_{o_i} ≥ f_{o_{i-1}} ≥ f_{g_{i-1}}). The greedy picks the earliest-finishing available interval, so f_{g_i} ≤ f_{o_i}.

Conclusion. If m > k, then by the claim f_{g_k} ≤ f_{o_k}, so o_{k+1} was available when the greedy stopped — contradicting the greedy’s rule. Therefore m ≤ k, and combined with optimality m ≥ k we get k = m. ∎

The exchange isn’t literal here — we never explicitly “swap” an element — but the structure is: the inductive hypothesis lets us implicitly exchange the optimum’s choices for the greedy’s, position by position, without ever hurting the count.

5.3 Worked example — Huffman Coding

(Full proof in Huffman Coding §5.)

The Huffman proof is two lemmas:

1. Greedy choice property. The two least-frequent symbols x, y can be made siblings at maximum depth in some optimal tree — proven by exchanging x (resp. y) with whatever leaf is currently at maximum depth, and showing the cost doesn’t increase.
2. Optimal substructure. If we treat x + y as a single composite symbol and the optimum for the smaller alphabet is T', then re-attaching x, y as children of T'’s composite-symbol leaf gives the optimum for the original alphabet.

Together: the greedy’s choice is consistent with some optimum, and the rest follows by induction. This is the cleanest “exchange argument” in the canon.

5.4 Worked example — Fractional Knapsack

(Full proof in Fractional Knapsack §5.)

Sort items by value/weight ratio descending. Greedy: take items in this order, with the last one possibly fractional.

Exchange. Suppose O is optimal and differs from the greedy at the first position i where they disagree. Either O uses less of item i than the greedy (since the greedy is taking the highest-ratio item available), in which case O must use more of some lower-ratio item j > i. Swap: take a small δ of item i (replacing δ · ratio_j of item j’s value with δ · ratio_i ≥ δ · ratio_j of item i’s value). The objective is at least as high, and the new O agrees with the greedy at position i. Repeat for i+1, i+2, … Eventually O = G. ∎

The exchange here is literal — swap a fraction of item j for a fraction of item i, and verify the value doesn’t drop.

6. Technique 2 — Greedy Stays Ahead

The greedy stays ahead technique is the close cousin of the exchange argument. The structure:

1. Let G be the greedy’s partial solution after k steps.
2. Let O be any other algorithm’s partial solution after k steps (typically the optimum’s first k elements).
3. Prove by induction on k that G is at least as good as O on some progress measure (e.g., G covers more, finishes earlier, accumulates more value).
4. Conclude the same at k = n, giving G ≥ O overall.

6.1 Difference from exchange

The exchange argument modifies an arbitrary optimum to match the greedy. “Greedy stays ahead” compares the greedy to any other strategy step-by-step without modifying anything — it’s a parallel-running invariant.

In practice the two techniques produce nearly-identical proofs for many problems; the choice is stylistic. The activity-selection proof in §5.2 is sometimes called “exchange,” sometimes “stays ahead” — really it’s both: at each step i, the greedy is no later than the optimum (stays-ahead invariant), which lets the exchange-style “the optimum’s choice was available to the greedy” argument run.

6.2 Worked example — Minimum Spanning Tree (Kruskal’s)

(See Kruskal’s Algorithm §5; this uses the cut property which is a structural strengthening of greedy-stays-ahead.)

Kruskal’s processes edges in non-decreasing weight order, accepting an edge if and only if it connects two different components. The proof: by induction, after processing the first k edges, the greedy’s accepted edges are contained in some minimum spanning tree (the cut property says the lightest edge crossing any cut is in some MST; Kruskal’s accepted edges all satisfy this).

6.3 Worked example — Dijkstra’s Algorithm

(See Dijkstra’s Algorithm for a full treatment.)

Dijkstra’s Algorithm’s correctness proof is “greedy stays ahead”: the invariant is that when a vertex v is removed from the priority queue, dist[v] is its true shortest-path distance. Inductively, this holds because v was the closest unvisited vertex, and any path to v going through an unvisited vertex would have to travel at least dist[v] to reach that unvisited vertex (which by induction has true distance ≥ dist[v]). The greedy “reaches each vertex with the true shortest distance” stays ahead of any wrong-order strategy.

The crucial caveat: Dijkstra’s stays-ahead invariant depends on non-negative edge weights. Negative edges break the monotonicity that makes the proof work — and that’s why Bellman-Ford is needed when edges can be negative.

7. The Matroid Theorem (Edmonds 1971) — The Deep Structural Result

The most beautiful theoretical result in greedy algorithms: a precise characterization of which problems admit an optimal greedy.

7.1 Definition of a matroid

A matroid M = (E, ℐ) is a pair where E is a finite ground set and ℐ ⊆ 2^E is a family of subsets (called independent sets) satisfying:

1. Non-empty: ∅ ∈ ℐ.
2. Hereditary (downward-closed): if A ∈ ℐ and B ⊆ A, then B ∈ ℐ.
3. Exchange property: if A, B ∈ ℐ and |A| < |B|, then there exists some x ∈ B \ A such that A ∪ {x} ∈ ℐ.

Walking through the symbols: E is the universe (e.g., the edges of a graph). ℐ is the collection of “valid partial solutions” (e.g., the edge-sets that don’t form a cycle — i.e., forests). The first axiom says the empty set is always valid. The second says every subset of a valid set is valid (you can always shrink). The third (the exchange axiom) is the deep one: if you have two valid sets and one is bigger, you can always extend the smaller by stealing one element from the bigger.

The exchange axiom is what makes greedy work: it guarantees that you can always grow a valid set toward a maximum valid set without getting stuck.

7.2 Examples of matroids

• Graphic matroid. E = edges of a graph; ℐ = forests (acyclic edge sets). The exchange property holds: any forest with fewer edges than another can be extended by an edge from the larger one without creating a cycle. This is why Kruskal’s works.
• Uniform matroid. E = any set; ℐ = subsets of size ≤ k. Trivially a matroid.
• Partition matroid. E partitioned into blocks E₁, …, E_p; ℐ = subsets that take at most k_i elements from each block.
• Linear matroid. E = vectors in a vector space; ℐ = linearly independent sets. (This is Whitney’s 1935 original example, which gave matroids their name.)
• Transversal matroid. Bipartite-matching-derived families.

7.3 The theorem

Theorem (Edmonds 1971; also Rado 1957 in a weaker form). Let M = (E, ℐ) be a matroid and w : E → ℝ be a weight function. The following greedy algorithm computes a maximum-weight independent set:

sort E in non-increasing order of w
S := ∅
for each e in sorted order:
    if S ∪ {e} ∈ ℐ:
        S := S ∪ {e}
return S

Conversely (Edmonds-Rado), if (E, ℐ) is hereditary and the greedy algorithm computes a maximum-weight independent set for every weight function w, then (E, ℐ) is a matroid.

The forward direction says “matroids ⇒ greedy works.” The converse is the surprise: “greedy works for every weight function ⇒ the underlying structure is a matroid.” So matroids aren’t just sufficient; they are exactly the structures on which greedy is universally optimal.

This explains, in one line, why so many “obvious” greedy algorithms work: they are running on a matroid. Kruskal’s runs on the graphic matroid. Maximum-weight basis selection in a vector space runs on the linear matroid. Job-scheduling-with-deadlines runs on a transversal matroid.

It also explains, in one line, why so many other obvious greedy algorithms don’t work: their underlying structure isn’t a matroid. Vertex cover is not a matroid (the independent sets of the “complement” structure — vertex covers — don’t satisfy the exchange axiom). Coin change with arbitrary denominations is not a matroid. The traveling salesman is not a matroid (the family of partial tours doesn’t satisfy the exchange axiom).

The two technical premises that make the converse hold — and that informal summaries routinely drop — are that the set family must be non-empty and hereditary (downward-closed) to begin with. Greedy-optimality-for-every-weight-function is what then forces it to be a matroid; without the hereditary premise the statement is false. This is exactly the form given by Edmonds (1971) and, in equivalent words, by Wikipedia’s matroid article: “if a family F of sets, closed under taking subsets, has the property that, no matter how the sets are weighted, the greedy algorithm finds a maximum-weight set in the family, then F must be the family of independent sets of a matroid” (Wikipedia: Matroid). For the textbook statement with proof see Korte & Vygen, Combinatorial Optimization, 5th ed., §13.4 (Theorem 13.19).

7.4 Greedoids — when matroids aren’t enough

A greedoid generalizes a matroid by relaxing the hereditary property; it’s the structure underlying some but-not-quite-matroid greedies (e.g., Dijkstra). The matroid intersection problem (find max independent set in two matroids simultaneously) is polynomial; the matroid union problem is polynomial; both produce algorithms that look greedier-than-greedy and are central to combinatorial optimization (see Korte & Vygen Ch. 13–14). For the interview, naming “greedoid” and “matroid intersection” demonstrates depth without needing to be able to prove the theorems.

8. When Greedy Fails — A Catalog of Counterexamples

The interview gold is this catalog: the candidate who knows where greedy fails is the candidate who won’t reach for it inappropriately.

8.1 Coin Change with Non-Canonical Denominations

(Already shown in §2.) D = {1, 3, 4}, n = 6: greedy gives 3 coins, optimal is 2. Fix: dynamic programming via Coin Change. The decision rule for “is greedy okay here?” is whether the denomination set is canonical, which is itself a non-trivial test (Pearson 2005 algorithm runs in O(n³) and is rarely worth doing — just use DP).

8.2 0/1 Knapsack

(See 01 Knapsack for the DP.) Items (value, weight): (60, 10), (100, 20), (120, 30) with capacity 50. Greedy by value/weight ratio picks item 1 (ratio 6) and item 2 (ratio 5), total value 160 with weight 30 — capacity 50 is not even filled because the ratio-3 item 3 (120/30 = 4) has weight 30 > remaining capacity 20. Optimum: items 2 and 3 give value 220 with weight 50.

The greedy fails because the 0/1 constraint (you take all of an item or none) makes the problem combinatorial. Fix: dynamic programming. The fractional version (where you can take any 0 ≤ x ≤ 1 of an item) IS greedy-solvable — see Fractional Knapsack — because removing the integrality constraint makes the problem a linear program whose optimum is at a vertex of the simplex, and the greedy is exactly the simplex method on this LP.

8.3 Vertex Cover

(Vertex cover: select the smallest set of vertices that touches every edge.) The “greedy” of repeatedly picking the highest-degree vertex gives an O(log n)-approximation, not the optimum. (See Vazirani, Approximation Algorithms, Ch. 2.) No polynomial greedy is known to solve vertex cover exactly — the problem is NP-hard. The structural reason: vertex covers don’t form the independent sets of any matroid.

The 2-approximation algorithm (pick any uncovered edge, take both endpoints, repeat) is not greedy in any meaningful sense — it doesn’t make locally-optimal choices, just locally-feasible ones. Be careful in interviews: “greedy” sometimes means “approximation algorithm with a simple loop,” and that’s not the same as “greedy that finds the optimum.”

8.4 Traveling Salesman

(TSP: find the minimum-cost Hamiltonian cycle.) The “nearest-neighbor” greedy — at each step, go to the nearest unvisited city — produces a tour that can be Θ(log n) times worse than optimal in the worst case (Rosenkrantz, Stearns, Lewis 1977). Even the more sophisticated “savings” heuristic of Clarke & Wright doesn’t give the optimum.

TSP is NP-hard. The greedies are heuristics giving useful but suboptimal answers; for the optimum, branch-and-bound, ILP, or specialized algorithms (Held-Karp O(n² · 2ⁿ)) are needed.

8.5 Set Cover

(Set cover: minimum number of sets whose union is the universe.) The greedy of picking the set covering the most uncovered elements gives an H_n-approximation (H_n is the harmonic number, ≈ ln n). Set cover is NP-hard, and the ln n factor is provably tight (Feige 1998). Not a counterexample to “greedy gives the optimum” — there’s no greedy for the optimum at all — but a worth-knowing example of greedy producing a useful approximate answer.

8.6 The “Activity Selection by Length” Wrong Greedy

Even within a problem where some greedy is optimal, the wrong greedy fails. Activity selection sorted by length picks [(1, 5), (4, 6), (5, 9)]’s middle interval first (length 2), eliminating two candidates for one. The right greedy (sort by finish time) picks 2 intervals.

Lesson: even the right problem doesn’t fix the wrong greedy key. You must prove the specific greedy you’re proposing works, not gesture at “it’s a greedy.”

9. Decision Checklist Before Reaching for Greedy

Before proposing a greedy in an interview or in production, walk through:

1. Can I name the greedy key precisely? (“Sort by finish time,” “sort by ratio,” “sort by frequency.”) If you can’t articulate the key, you don’t have a greedy yet.
2. Can I name the compatibility test? (“Doesn’t overlap last selected,” “doesn’t form a cycle,” “fits in remaining capacity.”) If the compatibility is “we’ll check at the end,” it’s not a greedy, it’s a feasibility filter.
3. Can I sketch an exchange argument? (“If the optimum picks o_i instead of my g_i, then I can swap them because…”) If you can’t even sketch why the swap is safe, the greedy is probably wrong.
4. Can I find a counterexample? Spend two minutes constructing one. If you can build a small input where greedy fails, your greedy is wrong; pivot to DP or another technique.
5. Is the problem on a known matroid? If yes, greedy works (Edmonds 1971); cite the matroid by name.
6. Is the problem known to be NP-hard? If yes, greedy at best gives an approximation; budget your time accordingly.

The senior interview signal is doing this checklist out loud before writing code. Even if you ultimately propose the greedy and write it, walking the interviewer through the checklist communicates that you understand when to reach for it — which is the actual rare skill.

10. Pitfalls

10.1 Confusing “Greedy” with “Heuristic”

A greedy algorithm produces a specific output deterministically and (when correct) provably optimally. A heuristic is a rule that often does well but has no optimality guarantee. The nearest-neighbor heuristic for TSP isn’t a “greedy that gets the optimum”; it’s a heuristic that’s O(log n)-from-optimum in the worst case. In interviews, distinguish carefully — calling a heuristic “greedy” without qualification suggests confused thinking.

10.2 Confusing “Greedy” with “Approximation Algorithm”

Some approximation algorithms (set cover greedy, vertex cover 2-approximation) are presented as “greedy” but are not optimal. Always state the approximation ratio alongside any greedy that doesn’t give the optimum.

10.3 Skipping the Proof

The most common interview failure: “I’ll sort by X and greedy on it.” That’s a guess, not a solution. Even if the greedy happens to be right, the interviewer wants to see the proof — usually a 30-second exchange-argument sketch.

10.4 Trying Greedy When DP is Required

The flag for DP: the optimal solution requires balancing competing concerns that a single sort can’t capture. Weighted interval scheduling, 0/1 knapsack, edit distance, longest common subsequence, coin change — all are DP, not greedy. The flag for greedy: the problem reduces to “always pick the locally-best candidate compatible with the partial solution.” If you find yourself wishing for a recurrence with two branches (“take or skip”), you’re in DP territory, not greedy.

10.5 Wrong Sort Order

Within a greedy, the sort key is half the algorithm. Sorting activity selection by start time fails; by length fails; only finish time works. Sorting fractional knapsack by value alone fails; by weight alone fails; only by ratio works. Always state the key explicitly and justify it.

10.6 Missing the Matroid

If a problem is on a matroid, calling out the structure (“this is the graphic matroid”) is the cleanest possible proof — the interviewer immediately knows the greedy is correct by Edmonds 1971. Even if you don’t recall the formal definition, recognizing structures like matroids is a strong senior signal.

10.7 Believing a Test-Suite Pass is a Proof

A greedy that passes 100 LeetCode test cases may still be wrong on some carefully-constructed input not in the suite. The proof — exchange argument, matroid structure, stays-ahead invariant — is what separates “got lucky on the tests” from “this algorithm is correct.” Interview problems sometimes have weak test cases that miss the counterexample for a wrong greedy.

10.8 Forgetting the Tie-Breaking Rule

If the greedy key has ties, the tie-breaking can determine correctness. In activity selection, ties in finish time are fine (any consistent tie-break works). In Huffman, ties in frequency produce different (but equally-optimal) trees. In some greedies — e.g., job scheduling with deadlines — the tie-break affects feasibility. Always specify the full ordering, including ties.

11. Diagram — The Two Proof Templates

flowchart TB
    Start([Want to prove greedy G is optimal])
    Start --> Choice{Pick a technique}
    Choice -->|Exchange Argument| EA[Take any optimal O.<br/>Show O can be transformed<br/>into G by a sequence of<br/>cost-preserving swaps.]
    Choice -->|Greedy Stays Ahead| GSA[For each step k, show<br/>greedy's partial solution<br/>is at least as good as<br/>any other algorithm's<br/>by induction on k.]
    EA --> Goal[G is optimal]
    GSA --> Goal
    Choice -->|Matroid Theorem| MT[Show E,I forms a matroid.<br/>Cite Edmonds 1971.<br/>Done.]
    MT --> Goal

What this diagram shows. Three formal routes to proving a greedy optimal: exchange (transform an optimum into the greedy’s solution preserving cost), stays-ahead (an inductive comparison between greedy and any alternative), and the matroid theorem (recognize the structure as a matroid and invoke Edmonds 1971). The first two are universal techniques applicable to any greedy; the third is a powerful shortcut when the underlying structure happens to be a matroid. All three converge on the same conclusion: the greedy’s output is globally optimal. The choice between them is largely stylistic — exchange argument is the most common in textbook presentations; stays-ahead is sometimes cleaner for online or step-by-step problems; matroid invocation is the deepest and most concise when applicable.

12. Common Interview Questions

Question	What’s being tested
”Prove your greedy is correct”	Exchange argument or stays-ahead sketch
”Why doesn’t greedy work for 0/1 Knapsack?”	Counterexample fluency
”When does greedy work for coin change?”	Knowledge of canonical denomination sets
”What’s a matroid? Give an example.”	Depth — Edmonds 1971 awareness
”Is X a matroid?” (typically MST, scheduling, vertex cover)	Mapping problem to structure
”Compare greedy vs DP for [problem]“	Decision rule for technique choice
”What’s the approximation ratio of greedy set cover?”	Understanding of approximation algorithms
”Construct a counterexample for greedy on [problem]“	Adversarial thinking

13. Open Questions

• Are there greedy algorithms that aren’t on matroids but still always optimal? Yes — some run on greedoids (a strict generalization). Dijkstra is the standard example. The full characterization is open in some flavors of “greedy.”
• Is recognizing a matroid in the wild a tractable skill? Mostly yes — the common matroids (graphic, partition, transversal, linear, uniform) cover most interview problems. The harder matroids (matching matroids, gammoids) rarely appear in interviews.
• What’s the relationship between greedy correctness and the simplex method? Fractional knapsack is the cleanest example — the greedy IS the simplex algorithm on the LP relaxation. More generally, every matroid-greedy can be seen as solving a linear program over the matroid polytope. This is the bridge from combinatorial greedy to convex optimization.

14. See Also

• Activity Selection — exchange-argument poster child
• Huffman Coding — exchange-argument with two lemmas
• Kruskal’s Algorithm — graphic-matroid greedy
• Prim’s Algorithm — same problem, different greedy, both correct via cut property
• Dijkstra’s Algorithm — greedy-stays-ahead with non-negative-edge caveat
• Fractional Knapsack — ratio greedy + LP perspective
• 01 Knapsack — counterexample to greedy, fix via DP
• Coin Change — counterexample to greedy with non-canonical denominations
• Memoization vs Tabulation — the alternative when greedy fails
• Interval Merging — greedy on intervals (different problem family)
• Gas Station — subtle exchange argument
• Jump Game — greedy stays-ahead variant
• Big-O Notation
• SWE Interview Preparation MOC