14.20 Proving Greedy Algorithms

Designing a greedy algorithm is often easier than proving it correct.

algorithmsgreedy

14.20 Proving Greedy Algorithms

Designing a greedy algorithm is often easier than proving it correct. Many rules appear reasonable:

Choose the earliest interval.
Choose the cheapest edge.
Choose the largest coin.
Choose the highest-value item.

Some of these rules are optimal. Others fail spectacularly.

The difference is not in the implementation. The difference is in the proof.

This chapter concludes the study of greedy algorithms by focusing on correctness proofs. Rather than introducing another algorithm, it summarizes the major proof techniques that appear throughout greedy algorithm design and shows how to recognize which technique applies.

Understanding these proofs is often more valuable than memorizing individual algorithms.

Why Greedy Proofs Matter

Consider two statements:

This algorithm seems to work.

and

This algorithm is optimal.

The gap between them is a proof.

Without a proof, a greedy algorithm is merely a heuristic.

With a proof, it becomes an exact algorithm.

The purpose of greedy analysis is to bridge that gap.

The Central Challenge

A greedy algorithm makes an irreversible decision.

Once chosen:

Take interval A.
Use edge E.
Schedule job J.

the algorithm never revisits that choice.

The proof must therefore show:

The chosen decision can safely belong to some optimal solution.

If that statement can be established repeatedly, the greedy algorithm is correct.

Proof Technique 1: Exchange Argument

The exchange argument is the most common greedy proof.

Basic idea:

  1. Assume an optimal solution exists.
  2. Show it can be modified.
  3. Replace part of it with the greedy choice.
  4. Preserve optimality.
  5. Repeat.

If every optimal solution can be transformed into one containing the greedy choice, the choice is safe.

Example: Interval Scheduling

Greedy rule:

Choose earliest finishing interval.

Suppose:

G

is the interval chosen by the algorithm.

Suppose:

O

is the first interval in an optimal schedule.

Because:

G

finishes no later than:

O

replacing:

O

with:

G

cannot reduce future scheduling opportunities.

Therefore an optimal schedule exists containing:

G

The greedy choice is safe.

Exchange Pattern

Most exchange arguments follow this template:

Optimal solution O

Replace component X

with greedy component G

Feasibility preserved
Objective unchanged or improved

Therefore:
Optimal solution containing G exists

This pattern appears throughout scheduling and optimization.

Proof Technique 2: Greedy-Choice Property

Some proofs focus directly on the first decision.

The goal is to show:

There exists an optimal solution whose first choice matches the greedy choice.

Once established:

  • Commit to that choice.
  • Remove it from consideration.
  • Solve the smaller problem.

Example: Fractional Knapsack

Greedy rule:

Take highest density item.

Suppose an optimal solution allocates capacity to a lower-density item while some higher-density capacity remains unused.

Exchange capacity.

Total value increases.

Contradiction.

Therefore some optimal solution must begin with the highest-density item.

The greedy-choice property holds.

Structure

The proof usually looks like:

Greedy first choice G

Assume optimal solution O

Show O can be modified
to include G

Therefore G is safe

This is closely related to exchange arguments but focuses specifically on the first step.

Proof Technique 3: Optimal Substructure

After proving the first choice is safe, we must show:

The remaining problem has the same structure.

This property is called optimal substructure.

Without it, the proof cannot continue recursively.

Example: Huffman Coding

After merging the two smallest frequencies:

x
y

the remaining problem becomes:

Build optimal Huffman tree
for reduced frequency set

The reduced problem is structurally identical to the original.

Therefore recursion is valid.

General Form

Optimal solution

=
Greedy choice

+
Optimal solution
to remaining problem

This decomposition appears repeatedly in algorithm design.

Proof Technique 4: Cut Property

Graph algorithms often require a different style of reasoning.

Instead of exchanges, they use cuts.

A cut partitions vertices into two groups.

Among all crossing edges:

Choose minimum-weight edge.

The cut property states:

The minimum crossing edge belongs to some minimum spanning tree.

Example: Kruskal

Greedy rule:

Choose smallest safe edge.

Proof:

  • Consider a cut.
  • Identify the minimum crossing edge.
  • Show replacing any heavier crossing edge cannot increase tree cost.

Therefore the minimum edge is safe.

This becomes the foundation of Kruskal and Prim.

Pattern

Partition graph

Identify minimum crossing edge

Prove edge belongs to
some optimal solution

This graph-specific proof technique is one of the most powerful greedy tools.

Proof Technique 5: Contradiction

Some greedy proofs proceed indirectly.

Assume:

Greedy solution is not optimal.

Then derive an impossibility.

Example: Earliest Deadline Scheduling

Assume a feasible schedule exists but the earliest-deadline schedule fails.

Examine the first position where schedules differ.

Swap jobs.

Show feasibility remains unchanged.

Eventually reach a contradiction.

Therefore the greedy schedule must be optimal.

General Pattern

Assume greedy fails

Construct contradiction

Therefore greedy succeeds

Contradiction proofs often accompany exchange arguments.

Proof Technique 6: Invariant-Based Proofs

Some greedy algorithms maintain a property throughout execution.

The proof focuses on preserving that invariant.

Example: Prefix Constraints

Invariant:

Current accepted jobs
form the best feasible set
for processed deadlines

Whenever a violation occurs:

Remove longest job

The proof shows:

  • Feasibility restored.
  • Optimality preserved.

The invariant remains true.

Structure

Invariant holds initially

Each step preserves invariant

Invariant implies correctness

Algorithm correct

This style is common in heap-based greedy algorithms.

Choosing the Right Proof

Different problems naturally suggest different proof techniques.

Problem Type Common Proof
Scheduling Exchange argument
Interval selection Exchange argument
Fractional optimization Greedy-choice property
Graph MST Cut property
Heap-based repairs Invariant
Ordering problems Contradiction + exchange
Recursive greedy Optimal substructure

Many proofs combine several techniques.

Example: Huffman Coding

Huffman coding uses:

Technique Role
Exchange argument Smallest frequencies become siblings
Greedy-choice property Safe merge
Optimal substructure Reduced problem remains Huffman problem

Several proof ideas work together.

Example: Kruskal

Kruskal uses:

Technique Role
Cut property Safe edge selection
Exchange argument Edge replacement
Optimal substructure Forest grows incrementally

Again, multiple proof methods interact.

Recognizing a Correct Greedy Algorithm

Before writing a proof, ask:

Can the Greedy Choice Appear in an Optimal Solution?

If not, the algorithm is probably incorrect.

Can I Transform an Optimal Solution?

Exchange arguments often emerge naturally.

Does the Remaining Problem Look the Same?

Optimal substructure is required.

Is There a Structural Theorem?

Graph problems frequently rely on cut properties.

Can I State an Invariant?

Heap-based algorithms often need one.

These questions guide the proof process.

Common Proof Mistakes

Proving Only Examples

A few successful examples do not establish correctness.

Assuming the Greedy Choice Is Obviously Best

The proof must connect local optimality to global optimality.

Ignoring Feasibility

Replacing one component may violate constraints.

Forgetting the Remaining Problem

A safe first choice alone is insufficient.

The proof must continue recursively.

Confusing Heuristics with Algorithms

A heuristic may perform well without any proof.

A greedy algorithm requires a correctness argument.

A Complete Greedy Proof Template

Most proofs can be organized into four steps.

Step 1

Identify the greedy choice.

Step 2

Show the choice is safe.

Use:

  • Exchange argument
  • Cut property
  • Contradiction
  • Greedy-choice property

Step 3

Show optimal substructure.

The remaining problem must have the same form.

Step 4

Apply induction.

If:

  • First choice is safe.
  • Remaining problem is solved optimally.

Then the entire solution is optimal.

This template covers the majority of classical greedy algorithms.

Relationship to the Entire Chapter

This chapter explored:

  • Interval scheduling
  • Activity selection
  • Huffman coding
  • Fractional knapsack
  • Job sequencing
  • Refueling stops
  • Prefix constraints
  • Graph greedy algorithms
  • String greedy algorithms

The algorithms differ dramatically.

The proofs do not.

Again and again, the same ideas appear:

Safe choice
Exchange
Reduction
Induction

Learning these proof patterns is the real goal of studying greedy algorithms.

Takeaway

Greedy algorithms are correct only when local decisions can be shown to participate in a globally optimal solution. The primary proof techniques are exchange arguments, greedy-choice properties, optimal substructure, cut properties, contradiction, and invariants. Although individual algorithms vary widely, their proofs often follow the same structure: identify a safe local choice, show that an optimal solution can include it, reduce the problem to a smaller instance, and continue recursively. Mastering these proof techniques provides a systematic framework for both designing and validating greedy algorithms.