14.1 Greedy Choice Property
The greedy choice property is the fundamental condition that allows a greedy algorithm to produce an optimal solution.
14.1 Greedy Choice Property
The greedy choice property is the fundamental condition that allows a greedy algorithm to produce an optimal solution. Informally, it states that there exists an optimal solution whose first decision matches the decision selected by the greedy algorithm. Once this decision is fixed, the remaining problem can be solved independently using the same reasoning.
Every successful greedy algorithm relies on this property. Without it, a locally attractive choice may eliminate the path to the global optimum. Understanding how to identify, prove, and exploit the greedy choice property is therefore the first step in designing greedy algorithms.
Problem
Given an optimization problem, determine whether a locally optimal decision can be safely chosen without examining all future possibilities.
Understanding Local and Global Optima
A greedy algorithm repeatedly selects the best available choice according to some rule.
Examples include:
- Choosing the earliest finishing interval.
- Selecting the smallest available edge.
- Taking the highest value-to-weight ratio item.
- Picking the nearest unvisited vertex.
The key question is:
Does choosing the best option now guarantee access to an optimal final solution?
For many problems the answer is no.
Consider the classic 0/1 knapsack problem.
| Item | Weight | Value |
|---|---|---|
| A | 10 | 60 |
| B | 20 | 100 |
| C | 30 | 120 |
Capacity = 50
A greedy strategy based on value density chooses:
| Item | Ratio |
|---|---|
| A | 6 |
| B | 5 |
| C | 4 |
The greedy solution selects A and B.
Total value:
60 + 100 = 160
The optimal solution is:
B + C = 220
The locally best choice destroys optimality.
This problem lacks the greedy choice property.
A Problem That Has the Property
Consider interval scheduling.
Given intervals:
| Interval | Start | End |
|---|---|---|
| A | 1 | 4 |
| B | 3 | 5 |
| C | 0 | 6 |
| D | 5 | 7 |
| E | 8 | 9 |
Goal:
Select the maximum number of non-overlapping intervals.
A natural greedy rule is:
Always choose the interval that finishes first.
Sorting by finishing time gives:
| Interval | Finish |
|---|---|
| A | 4 |
| B | 5 |
| C | 6 |
| D | 7 |
| E | 9 |
Choose A first.
Why is this safe?
Suppose an optimal schedule starts with another interval.
Because A finishes no later than any competing interval, we can replace the first interval of the optimal solution with A without reducing the number of intervals selected later.
The modified solution remains optimal.
Therefore an optimal solution exists that begins with A.
The greedy choice property holds.
Formal Definition
Let:
- (S) be the set of feasible solutions.
- (G) be the choice selected by the greedy rule.
- (O) be an optimal solution.
A problem satisfies the greedy choice property if:
There exists an optimal solution containing the greedy choice (G).
This statement may appear weak.
It does not require every optimal solution to contain (G).
Only one optimal solution needs to contain it.
That single optimal solution is enough to justify fixing the greedy choice permanently.
Structure of a Greedy Proof
Most correctness proofs follow the same pattern.
Step 1: Select the Greedy Choice
Identify the rule.
Examples:
- Earliest finish time.
- Smallest edge.
- Highest density item.
- Lowest cost connection.
Step 2: Consider an Optimal Solution
Assume an optimal solution exists.
Analyze its first decision.
Step 3: Exchange
Show that the first decision of the optimal solution can be replaced by the greedy decision.
The resulting solution remains feasible.
The objective value remains unchanged or improves.
Step 4: Reduce the Problem
After fixing the greedy decision, the remaining portion becomes a smaller instance of the same problem.
The process repeats.
This technique appears throughout the chapter.
Example: Fractional Knapsack
Items:
| Item | Weight | Value | Ratio |
|---|---|---|---|
| A | 10 | 60 | 6 |
| B | 20 | 100 | 5 |
| C | 30 | 120 | 4 |
Capacity = 50
Since fractions are allowed, selecting the highest ratio item first is always safe.
Suppose an optimal solution does not fully use item A.
Replace some lower-ratio weight with weight from A.
The total value increases.
The original solution therefore cannot be optimal.
An optimal solution must contain the greedy choice.
The greedy choice property holds.
This immediately yields the well-known algorithm:
Sort by value density.
Take as much as possible from each item.
Continue until capacity is exhausted.
Example: Minimum Spanning Trees
Consider a graph.
The greedy rule of Kruskal's algorithm is:
Select the smallest edge that does not create a cycle.
Why is this safe?
The cut property states:
The minimum-weight edge crossing any cut belongs to some minimum spanning tree.
Therefore the selected edge can always appear in an optimal solution.
This is exactly a greedy choice property.
Once the edge is chosen, the problem reduces to finding the remaining edges.
Recognizing the Property
Certain signals often indicate the presence of a greedy solution.
Ordering Matters
Many greedy algorithms begin with sorting.
Examples:
- Finish times.
- Edge weights.
- Deadlines.
- Ratios.
Sorting frequently exposes a dominant choice.
Exchange Is Easy
If two decisions can be swapped without harming optimality, exchange arguments often succeed.
Future Decisions Become Independent
After making the greedy choice, the remaining problem should resemble the original problem.
This self-similarity is essential.
Local Decisions Preserve Global Structure
The chosen element should not interfere with future optimal decisions.
When interference is small or controllable, greedy methods become possible.
Common Failure Patterns
Many problems appear greedy but are not.
Future Information Matters
Investment decisions, game trees, and many scheduling problems require looking ahead.
A locally attractive move may block a superior future opportunity.
Interactions Between Choices
In the 0/1 knapsack problem, selecting one item changes the value of all future capacity decisions.
Choices interact strongly.
No Valid Exchange Argument
If an optimal solution cannot be transformed to include the greedy choice, the property fails.
This usually means dynamic programming or search is required.
Recipe
When evaluating a potential greedy algorithm:
- Define the local rule.
- Construct small examples.
- Search for counterexamples.
- Assume an optimal solution exists.
- Attempt an exchange argument.
- Show the greedy choice can appear in some optimal solution.
- Reduce to a smaller instance.
- Repeat recursively.
If all steps succeed, a greedy algorithm is often possible.
Complexity Perspective
The greedy choice property frequently leads to dramatic efficiency improvements.
| Approach | Typical Complexity |
|---|---|
| Exhaustive search | Exponential |
| Dynamic programming | Polynomial |
| Greedy | Often (O(n \log n)) |
| Simple scan | Sometimes (O(n)) |
This reduction in complexity explains why proving the greedy choice property is one of the most valuable activities in algorithm design.
Takeaway
The greedy choice property states that a locally optimal decision can be fixed immediately because some globally optimal solution contains that decision. Most greedy correctness proofs revolve around demonstrating this fact through an exchange argument or structural theorem. Once established, the optimization problem collapses into a sequence of independent local decisions, allowing extremely efficient algorithms while preserving global optimality.