Greedy Algorithms

A greedy algorithm commits to one locally preferred choice without revisiting it. This is correct only when the problem structure proves that some optimal solution contains that choice.

Design workflow

1. Define feasible solutions and the objective precisely.
2. State the local choice rule and what remains afterward.
3. Prove the choice is safe.
4. Show the residual problem has the same structure.
5. Derive complexity from selection and update data structures.

Common proof patterns

• Exchange argument: replace part of an optimal solution with the greedy choice without making it worse.
• Stays ahead: after every prefix of choices, greedy is at least as good as any competitor under a useful measure.
• Cut property: a locally light edge is safe across a suitable partition.
• Induction: after proving the first safe choice, apply the same reasoning to the residual instance.

Representative problems

Problem	Safe choice	Required structure
Activity selection	earliest finish	maximize count of compatible intervals
Fractional knapsack	highest value density	divisible items, linear value
Huffman coding	merge two least frequent nodes	binary prefix-code objective
MST	safe light edge across a cut	weighted undirected graph
Dijkstra	settle minimum tentative distance	nonnegative edge weights

Greedy coin selection, highest immediate profit, or smallest immediate cost can fail on arbitrary instances. A plausible rule is a conjecture until a proof or known structural theorem supports it.

Greedy versus dynamic programming

Dynamic programming compares alternatives across reusable states. Greedy collapses those alternatives using a safe-choice theorem. When the exchange property fails, retaining more state may be necessary.

A failed rule and the state it leaves behind

With unlimited denominations 1, 3 and 4, largest-first makes amount 6 as 4+1+1, but 3+3 uses fewer coins. The local rule discards the latter choice without a valid exchange argument: replacing two 3s by a 4 leaves a remainder requiring two more coins.

A dynamic program keeps dp[t], the fewest coins for exact amount t, and considers every possible last coin: dp[t] = min(1+dp[t-c]) over denominations c no larger than t. Initialize dp[0]=0 and impossible amounts to infinity. For amounts 0..6, the table is [0,1,2,1,1,2,2]. This solves the stated positive-integer, unlimited-use model in O(Tk) time and O(T) space. Greedy's failure does not force DP in every problem: exhaustive search or another structural algorithm may be more appropriate.

Source

• MIT OpenCourseWare: Greedy Algorithms

My reading · Opened notes are remembered in this browser.