Greedy — exchange argument proof technique: Question bank

Notation used on this page (read first)

Definition Every symbol, in plain words

$G = (g_{1}, g_{2}, \dots, g_{n})$ — the sequence of choices the greedy algorithm makes, in order. $g_{i}$ is greedy's $i$ -th choice.
$O = (o_{1}, o_{2}, \dots, o_{n})$ — any optimal solution, written as an ordered sequence; $o_{i}$ is its $i$ -th choice.
$O^{'}$ — the solution you get after doing one swap inside $O$ .
$OPT$ — the best achievable objective value (what optimal $O$ scores).
$p_{k}$ — the processing time (length) of job $k$ . $w_{k}$ — its weight (importance) in weighted problems.
$C_{k}$ — the completion time of job $k$ : the clock time at which it finishes. $C_{a}, C_{b}$ are the completion times of two specific jobs $a, b$ .
$f_{k}$ — the finish time of activity $k$ in interval problems. $f_{g_{1}}$ = finish time of greedy's first pick, $f_{o_{1}}$ = finish time of optimal's first pick.
In Huffman: $f (c)$ = frequency of symbol $c$ ; $depth (c)$ = its depth in the code tree.

The diagram below shows this chain shrinking the disagreements down to zero.

Figure — Greedy — exchange argument proof technique

Recall Statements of the tools referenced below (so you needn't chase links)

Smith's rule: to minimise weighted completion time $\sum_{k} w_{k} C_{k}$ , schedule jobs in increasing order of the ratio $p_{k} / w_{k}$ . Plain SPT (sort by $p_{k}$ ) is the special case $w_{k} = 1$ .
Huffman sibling lemma: in some optimal prefix-code tree, the two lowest-frequency symbols $x, y$ are sibling leaves at maximum depth. Proved by two swaps ( $x \leftrightarrow a$ , $y \leftrightarrow b$ ) whose combined cost change $Δ \leq 0$ .
Exchange chain: the sequence $O_{0} \to \dots \to G$ above, each link no worse than the last.

Before you start, keep three obligations of every exchange proof in mind — they recur constantly:

Recall The three things an exchange proof must always establish

(1) The swapped solution $O^{'}$ is still feasible (a legal solution). (2) $O^{'}$ is no worse than $O$ . (3) $O^{'}$ agrees with greedy in one more place, so induction terminates at $G$ . Miss any one and the proof is broken.

True or false — justify

An exchange argument proves greedy is optimal by improving greedy's own output

False — you never touch

G

; you take an arbitrary optimal

O

and edit it toward

G

, showing

G

is no worse than

O

If a single swap makes the objective strictly better, the original solution could not have been optimal

True — that is a contradiction: an optimal solution admits no strictly-improving edit, so the configuration you swapped away (an inversion) cannot exist in any optimum.

A swap that leaves the objective exactly equal is useless for the proof

False — "equal" is enough; it shows some optimum agrees with greedy one more place, which is all counting problems like activity selection need.

Exchange arguments and greedy-stays-ahead are the same technique with different names

False — stays-ahead is a measure-based induction showing greedy is never behind; exchange physically swaps elements in

O

. Both prove optimality but by different mechanisms.

The exchange argument requires the objective to be a sum

False — it requires that a local swap changes only a bounded, computable piece of the objective; sums make this easy but any objective with that locality works.

Once you show one swap doesn't hurt, you are done

False — you must also argue the swaps terminate: each reduces the number of disagreements with

G

, so finitely many reach

G

(that is the exchange chain).

For weighted completion time, sorting by processing time

p_{k}

is still optimal

False — the correct order is by ratio

p_{k} / w_{k}

(Smith's rule);

p_{k}

alone is the special case

w_{k} = 1

In the Huffman sibling lemma, showing the single swap

x \leftrightarrow a

\leq 0

finishes the proof

False — the construction performs two swaps (

x \leftrightarrow a

and

y \leftrightarrow b

); you must show the sum

Δ

of both cost-change terms is

\leq 0

Every greedy algorithm can be proven correct by an exchange argument

False — some need matroid theory or a DP-based comparison; exchange is the workhorse for ordering/scheduling but not universal.

If greedy and optimal agree at every index, no swap is needed

True — that is the base case; there is no first disagreement, so

G = O

and

cost (G) = OPT

Spot the error

"I swapped two jobs and cost dropped, so greedy is better than optimal."

The error: optimal cannot be beaten, so this means the starting solution was not optimal — the swap proves an inversion is impossible in any optimum, not that greedy beats OPT.

"I picked any index where

G

and

O

differ and swapped there."

The error: you must swap at the first disagreement (smallest

i

with

g_{i} \neq = o_{i}

) so the already-matching prefix is preserved; an arbitrary index breaks the induction toward

G

"In activity selection I replaced

o_{1}

g_{1}

and just checked the count went up."

The error: forgetting feasibility — you must first argue

f_{g_{1}} \leq f_{o_{1}}

so later activities still fit; only then is the equal count meaningful.

"For SPT I computed only

C_{a}

changes when I swap adjacent

a, b

The error: both

C_{a}

and

C_{b}

change; jobs before

a

and after

b

are untouched, but the pair's two completion times both shift, and the difference

p_{a} - p_{b}

comes from both.

"The swap changed jobs far from the swapped pair too, so I recomputed the whole schedule."

The error (opposite mistake): for an adjacent swap, jobs outside the pair keep identical completion times; recomputing everything is wasted work and hides the clean

p_{a} - p_{b}

result.

"Greedy is locally optimal at each step, so it must be globally optimal."

The error: local ≠ global; coin change with

{1, 3, 4}

making

6

gives greedy

4 + 1 + 1

(3 coins) vs optimal

3 + 3

(2). Only a contradiction/exchange proof certifies correctness.

"My exchange proof shows

O^{'}

is no worse, so I'm done — I'll skip checking

O^{'}

is legal."

The error: a "no worse" solution that violates constraints proves nothing; feasibility is a separate, mandatory obligation.

"In Huffman I assumed

a, b

are the smallest-frequency leaves."

The error:

x, y

are the smallest-frequency symbols;

a, b

are the deepest sibling leaves. These are generally different, and the whole lemma is about relating them.

Why questions

Why must

g_{i}

appear somewhere later in

O

before we can swap

Because greedy never wastes a choice, the element

g_{i}

is part of the solution set, so if

O

is optimal it contains

g_{i}

at some position

j > i

to swap into place

i

Why does putting the shorter job first reduce

\sum C_{k}

The job finishing second "pays" the first job's length inside its completion time; making the first job the shorter one shrinks that doubled contribution, so the sum drops by

p_{a} - p_{b}

Why does the exchange chain guarantee

cost (G) \leq OPT

Each link of the chain

O_{0} \to \dots \to G

satisfies

cost (O_{i + 1}) \leq cost (O_{i})

; telescoping the inequalities gives

cost (G) \leq cost (O) = OPT

Why is "earliest finish time" the right greedy criterion for activity selection

Because

f_{g_{1}} \leq f_{o_{1}}

guarantees any activity compatible with

o_{1}

is still compatible with

g_{1}

, so the swap preserves feasibility — the criterion is chosen precisely to make obligation (1) automatic.

Why does the weighted inversion swap change cost by

w_{b} p_{a} - w_{a} p_{b}

Swapping adjacent

a, b

moves

b

earlier (saving

w_{b} p_{a}

) and

a

later (costing

w_{a} p_{b}

); the net is

w_{b} p_{a} - w_{a} p_{b}

, non-negative exactly when

p_{a} / w_{a} \geq p_{b} / w_{b}

Why do we need induction and not just one swap

One swap fixes only the first disagreement; induction on the matching prefix repeats the argument until the whole solution equals

G

Why is the objective decrease in Example 1 strict but in Example 2 only weak

SPT is a minimisation with distinct lengths so removing an inversion strictly lowers cost; activity selection counts picks, so a same-count replacement is only "no worse", not strictly better.

Edge cases

What if two jobs have equal processing time,

p_{a} = p_{b}

The swap gives

cost

difference

p_{a} - p_{b} = 0

; both orders are optimal, so greedy's tie-breaking is harmless and the "no inversions" statement still holds weakly.

What if

O

already equals

G

from the start

Then there is no first disagreement; the induction base case applies and

cost (G) = cost (O) = OPT

trivially.

What if all activities in the selection problem are mutually overlapping

Greedy picks exactly one (the earliest-finishing); the optimum is also one, and the single replacement

o_{1} \to g_{1}

shows they match.

What if a job has length zero,

p_{k} = 0

It contributes

0

to any doubled term and never creates a beneficial inversion; SPT places it first harmlessly and the proof is unaffected.

What if the Huffman alphabet has size one (a single symbol)

There is no sibling pair, so the swap in the lemma cannot even be set up; this is a degenerate base case — a one-symbol code is a single leaf of depth

0

, trivially optimal, and the lemma simply doesn't apply until the alphabet has

\geq 2

symbols.

What if the two smallest Huffman frequencies are equal,

f (x) = f (y)

Both terms of

Δ

still evaluate to (non-negative)

\times

(non-positive)

\leq 0

; ties just mean multiple optimal trees exist, all reachable by the swap.

What if in Huffman the smallest symbols are already the deepest siblings

Then

x = a

y = b

, the depth differences are

0

, so

Δ = 0

and no swap is needed — the base configuration already satisfies the lemma.

What if there is only one job (or one activity)

There is nothing to swap; greedy's single choice is trivially the only feasible solution, hence optimal.

What if weights are all equal in Smith's rule

The ratio

p_{k} / w_{k}

reduces to

p_{k}

(times a constant), recovering plain SPT — the unweighted case is Smith's rule specialised to

w_{k} = 1