Exercises — Greedy — exchange argument proof technique

Greedy-stays-ahead. It tracks a measure (how far along you are after $k$ picks) and shows greedy's measure dominates optimal's at every $k$. An exchange argument instead physically edits the optimal solution one swap at a time. See Greedy-stays-ahead proof technique for the contrast.

Adjacent pairs and whether the earlier one is longer (an inversion under the SPT rule):

• $A(5)\to B(2)$: $5>2$ → inversion ✔
• $B(2)\to C(9)$: $2<9$ → fine
• $C(9)\to D(3)$: $9>3$ → inversion ✔

Two adjacent inversions: $(A,B)$ and $(C,D)$.

In $O$ ($a$ then $b$): $C_a=t+p_a=4+7=11$; $C_b=t+p_a+p_b=4+7+3=14$. Sum $=25$. In $O^{\prime }$ ($b$ then $a$): $C_b=t+p_b=4+3=7$; $C_a=t+p_b+p_a=4+3+7=14$. Sum $=21$. Improvement $=25-21=4=p_a-p_b=7-3$. Matches the formula $\text{cost}(O)-\text{cost}(O^{\prime })=p_a-p_b$.

The picture (Figure s01) makes the "paid twice" idea visible. Read it as follows: each row is a schedule, each block's width is its processing time $p$, and the red arrow points at the finish time that gets counted inside both $C$-values (the first job's length is added again to the second job's completion). In the top row ($O$) that doubled length is the long red bar's $p_a=7$; in the bottom row ($O^{\prime }$) it is the short green bar's $p_b=3$. So the figure shows geometrically why the total drops by exactly $p_a-p_b$: you shrink the length that is charged twice. Without the figure the "$2p_a$ vs $2p_b$" doubling is just algebra; with it you see which bar is doubled.

Where the formula comes from. Let the pair start at time $t$ (the start of whichever job runs first). In order $a$-then-$b$: $C_a=t+p_a$ and $C_b=t+p_a+p_b$, so the pair contributes $w_a(t+p_a)+w_b(t+p_a+p_b)$. In order $b$-then-$a$: the contribution is $w_b(t+p_b)+w_a(t+p_b+p_a)$. Subtracting, every term containing $t$ cancels (both jobs still start no earlier than $t$), leaving $\text{cost}(a\text{-first})-\text{cost}(b\text{-first})=w_b{p}_a-w_a{p}_b.$ That is why the messy expression collapses to this clean cross-difference: it isolates exactly the mutual-waiting penalty.

Plug in. $w_b{p}_a-w_a{p}_b=3\cdot 6-2\cdot 4=18-8=10>0$. Positive means the current order ($a$ then $b$) costs more — swapping helps by $10$. Equivalently, $p_a/w_a=6/2=3$ and $p_b/w_b=4/3\approx 1.33$; since $3>1.33$, job $a$ has the worse ratio and should go later. This is Smith's rule — weighted completion time.

Tie case: if $p_a/w_a=p_b/w_b$ then $w_b{p}_a-w_a{p}_b=0$ — either order is equally good, so break ties arbitrarily.

• SPT minimises a sum of real quantities ($\sum C_k$). A genuine inversion ($p_a>p_b$) makes the swap strictly cheaper by $p_a-p_b>0$. Strictness lets us argue by contradiction: an optimal schedule cannot contain an inversion, else we'd beat it. (At a tie $p_a=p_b$ the change is $0$ — not an inversion, nothing to fix.)
• Activity selection counts activities. Replacing $o_1$ by the earlier-finishing $g_1$ keeps the count identical (one-for-one), so the swap is weakly no-worse. It preserves optimality rather than improving it, then we induct on the remainder — see Activity Selection Problem.

Both work because the exchange contract only requires "no worse." Strict improvement is a bonus (and enables the contradiction phrasing); equality is enough to carry optimality along the swap chain $O\to O_1\to \cdots \to G$.

Where each $\Delta$ comes from. Cost is ${\sum }_{c}f(c)d_c$ (here $f(c)$ is a symbol's frequency and $d_c$ its depth in the tree). Swapping symbols $x$ and $a$ means $x$ now sits at depth $d_a$ and $a$ at depth $d_x$; every other symbol keeps its depth, so all those terms cancel in the difference. Only the two moved symbols survive: ${\Delta }_1=[f(x)d_a+f(a)d_x]-[f(x)d_x+f(a)d_a]=(f(a)-f(x))(d_x-d_a).$ That factored form is why the swap is easy to sign: it is a product of a frequency gap and a depth gap. The same algebra with $y,b$ gives ${\Delta }_2=(f(b)-f(y))(d_y-d_b)$.

Plug in. First swap: ${\Delta }_1=(f(a)-f(x))(d_x-d_a)=(4-1)(2-5)=3\cdot (-3)=-9$. Second swap: ${\Delta }_2=(f(b)-f(y))(d_y-d_b)=(3-2)(1-5)=1\cdot (-4)=-4$. Total $\Delta =-9+(-4)=-13\le 0$. Cost strictly decreases here. Each factor pattern: $(f(\text{deep})-f(\text{shallow-symbol}))\ge 0$ times $(d_{\text{shallow-symbol}}-d_{\text{deep}})\le 0$ gives a non-positive product. Tie case: if a frequency gap is $0$ (equal frequencies) or a depth gap is $0$, that term is exactly $0$ — still no increase. Summing both is mandatory — see Huffman Coding.

1. Setup. Let $O$ be any optimal schedule, $G$ the SPT schedule. 2. First difference. If $O=G$, done. Otherwise $O$ differs from sorted order, so it contains at least one adjacent inversion: jobs $a$ then $b$ with $p_a>p_b$. (If no adjacent pair were inverted, the whole order would be sorted = $G$.) 3–4. Swap. Exchange the adjacent pair $a,b$ to get $O^{\prime }$. Every job before $a$ and after $b$ keeps its exact start time, so only $C_a,C_b$ change — feasibility holds (still one job at a time). 5. No worse. Let $t$ be the start time of job $a$ in $O$ (equivalently, the start time of the adjacent $a,b$ block, since $b$ runs immediately after $a$). In $O$: $C_a=t+p_a$, $C_b=t+p_a+p_b$, so their sum is $2t+2p_a+p_b$. In $O^{\prime }$: $C_b=t+p_b$, $C_a=t+p_b+p_a$, sum $2t+2p_b+p_a$. Hence $\text{cost}(O)-\text{cost}(O^{\prime })=(2p_a+p_b)-(2p_b+p_a)=p_a-p_b>0.$ So $O^{\prime }$ is strictly cheaper — impossible if $O$ was optimal and had an inversion. Therefore optimal has no inversion, i.e. it is sorted by SPT $=G$. Hence $G$ is optimal. $■$ Tie case: if $p_a=p_b$ the difference is $0$ — the two orders cost the same, so equal-length jobs may sit in either order and SPT (breaking ties arbitrarily) is still optimal. (The adjacency-only argument suffices because any inversion implies an adjacent one — see L1.2.)

Notation for this proof. Each activity $i$ is an interval $[s_i,f_i)$, where $s_i$ is its start time (when it begins) and $f_i$ is its finish time (when it ends). (This $f$ is a finish-time — unrelated to the frequency $f(\cdot )$ used in the Huffman exercise L3.2.) Setup. Let $O=(o_1,o_2,\dots )$ be optimal, its activities sorted by finish time. Let $g_1$ be the activity with the smallest finish time of all activities, so $f_{g_1}\le f_{o_1}$. Swap. Form $O^{\prime }$ by replacing $o_1$ with $g_1$, keeping $o_2,o_3,\dots$. Feasibility. In $O$, activity $o_2$ starts at $s_{o_2}\ge f_{o_1}$ (they don't overlap). Since $f_{g_1}\le f_{o_1}\le s_{o_2}$, activity $o_2$ still starts after $g_1$ finishes. $g_1$ vs $o_2$: compatible. All later activities were already after $o_1$, hence after $g_1$. So $O^{\prime }$ is a valid (pairwise non-overlapping) selection. No worse. $|O^{\prime }|=|O|$ (swapped one for one), so $O^{\prime }$ is also optimal and it contains $g_1$. Tie case: if two activities share the globally earliest finish time, either may serve as $g_1$; the same $f_{g_1}\le f_{o_1}$ argument holds, so the choice is free. Induct on the subproblem of activities starting after $f_{g_1}$: the same lemma applies, so greedy's every pick is extendable to an optimum. $■$

Notation for this proof. A "slot" is a unit time interval; a job placed in slot number $m$ finishes at $C=m$. Consider two adjacent jobs $a,b$ where $O$ runs $a$ in slot $m$ and $b$ in slot $m+1$.

Derive the swap change. Swapping puts $b$ in slot $m$ and $a$ in slot $m+1$. Only these two jobs move slots, so all other penalties cancel in the difference: $\Delta =\left[\underset{\text{order }a,b}{\underbrace{w_{a}m+w_b(m+1)}}\right]-\left[\underset{\text{order }b,a}{\underbrace{w_{b}m+w_a(m+1)}}\right].$ Expand: the $m$-terms give $w_{a}m+w_{b}m-w_{b}m-w_{a}m=0$ (the slot index $m$ cancels entirely, since both jobs still occupy the same two slots), and the $+1$ terms give $w_b-w_a$. So $\Delta =w_b-w_a.$

Read off the key. Swapping helps (lowers cost) when $\Delta <0$, i.e. when $w_a<w_b$: a lighter job sitting before a heavier one should be swapped so the heavier one moves earlier. Therefore the greedy rule is sort by weight, descending — largest weight first.

Proof (exchange argument). Take any optimal schedule $O$. If $O$ ever runs a lighter job immediately before a heavier one ($w_a<w_b$ with $a$ before $b$), the adjacent swap above lowers cost by $w_b-w_a>0$, contradicting optimality. Hence optimal contains no such inversion, so it is sorted by descending weight $=G$. Therefore $G$ is optimal. $■$

Tie case: if $w_a=w_b$ then $\Delta =0$ — equal-weight jobs may occupy either slot; break ties arbitrarily. (This is Smith's rule with all $p_k=1$: the ratio $p_k/w_k=1/w_k$ ascending $\iff$ weight descending.)

Greedy-by-largest: $4+1+1=3$ coins. Optimum: $3+3=2$ coins. Greedy is not optimal. No exchange argument works because the problem lacks the exchange property: swapping a single greedy coin for another does not monotonically improve — the optimum $\{3,3\}$ shares no coin with greedy's first choice ($4$), so there is no local swap chain $O\to \cdots \to G$ that stays feasible and no-worse. When the greedy/exchange (or matroid) structure is absent, we need the overlapping-subproblem machinery of DP.

Every exchange proof I write states the objective ::: yes — the number being optimised is named before any swap I swap at the first disagreement and induct on the matching prefix ::: yes I check feasibility of $O^{\prime }$, not only its cost ::: yes If the construction does two swaps I sum both $\Delta$ terms ::: yes I know strict-improvement (contradiction) vs equal-cost (preserve) are both valid ::: yes At a tie in the greedy key the swap change is exactly $0$, so ties break arbitrarily ::: yes