Foundations — Greedy — exchange argument proof technique

This page is the ground floor of the exchange-argument note. Before you can read a single line of that proof, you need to own every symbol it throws at you. We build each one from a picture — no symbol appears here until you have seen what it means.

0. The scene: what problem are we even in?

Almost every exchange proof lives in a scheduling or choosing world. Picture a single machine — a printer, a CPU, one busy person — that can do only one task at a time. You have a pile of jobs. You must decide the order to do them in. Different orders cost different amounts. We want the cheapest order.

A greedy rule is a simple recipe for deciding the order without looking ahead: at each step, pick the job that scores best on one fixed criterion. Two greedy rules you will meet in the parent note:

• Shortest-Job-First (SPT): always run the shortest not-yet-done job next.
• Smallest-ratio-first (Smith's rule): always run the job with the smallest $p_k/w_k$ next (used when jobs have importance weights — see §4).

Everything below is vocabulary for talking about that picture precisely.

1. A job and its length $p_k$

• Plain words: $p_k$ = "how long job number $k$ takes."
• Picture: in Figure 1 each job is a coloured bar; the width of the bar is $p_k$. A wide bar = a long job.
• Why we need it: the whole game is about ordering jobs, and the cost depends on how long each one takes. Without lengths there is nothing to optimise.

The little $k$ hanging below $p$ is a subscript — it is not multiplication. $p_k$ is read "p-sub-k" and just means "the $p$ belonging to job $k$." So $p_3$ is the length of job 3.

2. Completion time $C_k$

• Plain words: "what time is it when job $k$ is done?"
• Picture: below.
• Why we need it: the cost we minimise is built out of these finish-times. It is the number the whole topic cares about.

The key insight the picture shows: a job's completion time is the sum of the lengths of every job at or before it in the order. If the order is job A (length 3), then job B (length 2), then: $C_A=3,C_B=3+2=5.$ Job B had to wait for A to finish first — that waiting is baked into $C_B$. This is exactly why order matters.

3. The sum symbol $\sum$

• Plain words: ${\sum }_{k=1}^n{C}_k=C_1+C_2+C_3+\cdots +C_n$ — one term per job, no job left out.
• Picture: stack every job's finish-time and total the heights.
• Why we need it: our objective — the thing we minimise — is the total completion time ${\sum }_{k=1}^n{C}_k$. It rewards finishing jobs early, because an early finish is a small number added to the pile.

4. Weight $w_k$ and the ratio $p_k/w_k$

• Plain words: importance dial for each job.
• Picture: in the sunset figure, imagine each bar also has a brightness — brighter = more important = higher weight.
• Why we need it: the general objective is the weighted total ${\sum }_{k=1}^n{w}_k{C}_k$: an important job finishing late costs a lot, an unimportant one finishing late costs little. When all $w_k=1$ this collapses back to plain ${\sum }_{k=1}^n{C}_k$.

The parent note's mistake-box uses the ratio $\frac{p_k}{w_k}$ ("length divided by importance"). Small ratio = short and important = do it first. This is Smith's rule (see Smith's rule — weighted completion time).

5. The number of jobs $n$, and two solutions $G$ (greedy) and $O$ (optimal)

• Plain words: $n$ = "how many jobs there are"; $G$ = "what greedy does"; $O$ = "a true champion answer." Both lists contain exactly the same $n$ jobs — only the order differs.
• Picture: two rows of the same coloured bars, possibly in different left-to-right orders.
• Why we need it: the whole proof compares these two lists position by position. The parentheses $(g_1,\dots ,g_n)$ are just an ordered list — $g_1$ is the first thing done, $g_n$ the last. The subscript is a position, not a job number.

6. Cost and OPT

• Plain words: $\text{cost}(\cdot )$ = a machine that eats any ordering and spits out its price tag; $\text{OPT}$ = the lowest price tag that exists.
• Why we need it: "optimal" is defined by $\text{cost}(O)=\text{OPT}$. The proof's punchline is $\text{cost}(G)=\text{OPT}$, i.e. greedy hits the best price.

7. The inequality $\le$ and "no worse"

The engine of every exchange proof is one inequality: $\text{cost}(O^{\prime })\le \text{cost}(O)$.

• Picture: a see-saw that after the swap tips down or stays level, never up.

8. The swap (exchange) itself, and an inversion

• Picture: below — grab two bars, cross the arrows, put each where the other was.
• Why we need it: the proof repeatedly removes inversions by swapping. Each swap fixes one disagreement between $O$ and $G$.

Because only the swapped pair moves, only their completion times change — every other job starts and ends at the same clock time. That is what makes the cost change easy to compute (just two terms).

9. First difference, index $i$, twin at position $j$

• Plain words: find the earliest spot the two lists differ; drag greedy's choice from wherever it hides in $O$ up to that spot.
• Why the first difference: so that the part already matching greedy stays matched. This lets us make steady progress toward $G$ and guarantees the process stops (finitely many disagreements, each swap kills one). See the Induction idea below.

10. Telescoping and the final chain

• Plain words: a domino line of orderings, each no worse than the one before, starting at an optimal $O$ and ending exactly at $G$ after $m$ steps.
• Picture: a staircase that only ever steps down or flat.

11. Two proof flavours you'll meet

Both live under the umbrella of greedy algorithms, and both are alternatives to (usually heavier) dynamic programming proofs.

Prerequisite map

Equipment checklist

Cover the right side; can you answer each before reading it?

Next: return to the parent note and read the 5-step skeleton — every symbol there is now yours.