Greedy — exchange argument proof technique

3.7.3 · Coding › Algorithm Paradigms

WHAT hai exchange argument?

Do flavours hain jo tumhe pehchanne chahiye:

Greedy-stays-ahead — dikhao ki greedy $k$ steps ke baad optimal se kabhi peeche nahi (ek measure-based induction).
Exchange/swap — $O$ mein do elements ko physically swap karo aur prove karo ki objective worse nahi hoti.

Yeh note swap flavour ke baare mein hai, jo ordering/scheduling problems ka workhorse hai.

WHY karta hai swapping optimality prove?

Asal reason: tum ek chain bana rahe ho $O = O_{0} \to O_{1} \to \dots \to O_{m} = G, cost (O_{i + 1}) \leq cost (O_{i}) .$ Telescoping: $cost (G) \leq cost (O) = OPT$ . Kyunki $OPT$ best possible hai, $cost (G) = OPT$ .

HOW karo exchange proof (recipe)

Poora game step 5 mein rehta hai — aur woh hamesha uss inequality pe aata hai jo greedy choice ko define karti hai.

Worked Example 1 — Total completion time minimize karo

Problem. $n$ jobs, job $k$ ki length $p_{k}$ hai. Ek baar mein ek chalao. (Unweighted) total completion time $\sum_{k} C_{k}$ minimize karo, jahan $C_{k}$ = job $k$ ka finish time. Greedy: Shortest Processing Time first (SPT). (Agar har job ka weight $w_{k}$ bhi ho aur objective $\sum_{k} w_{k} C_{k}$ ho, toh sahi greedy ratio $p_{k} / w_{k}$ se sort karti — neeche mistake box dekho.)

Worked example SPT ke liye exchange proof

Setup. $O$ ko optimal maano. Maano $O$ ek job $a$ ko ek job $b$ se immediately pehle chalata hai jahan $p_{a} > p_{b}$ (ek "inversion" — longer pehle, shorter baad mein). Greedy yeh forbid karti hai.

Swap. $O$ mein $a$ aur $b$ ko swap karo $O^{'}$ banane ke liye. Yeh step kyun? $a$ se pehle aur $b$ ke baad schedule hue saare jobs unchanged hain, isliye sirf $C_{a}, C_{b}$ change hote hain.

$t$ = pair ka start time maano. Tab:

$O$ mein: $C_{a} = t + p_{a}$ , $C_{b} = t + p_{a} + p_{b}$ . Sum $= 2 t + 2 p_{a} + p_{b}$ .
$O^{'}$ mein: $C_{b} = t + p_{b}$ , $C_{a} = t + p_{b} + p_{a}$ . Sum $= 2 t + 2 p_{b} + p_{a}$ .

Yeh step kyun? Jo job second finish hoti hai woh dusre ki length pay karti hai, isliye shorter job pehle rakhne se doubled term reduce hoti hai.

Difference: $cost (O) - cost (O^{'}) = (2 p_{a} + p_{b}) - (2 p_{b} + p_{a}) = p_{a} - p_{b} > 0.$

Toh $O^{'}$ strictly better hai — jo optimality ke contradiction mein hai jab tak koi inversion exist kare. Isliye optimal mein koi inversion nahi, yaani woh SPT se sort hai. ∎

Worked Example 2 — Activity selection (earliest finishing time)

Problem. Intervals $[s_{k}, f_{k})$ ; max number of non-overlapping wale chuno. Greedy: baar baar compatible activity lo jiski earliest finish time ho.

Worked example Exchange proof

Setup. $O = (o_{1}, o_{2}, \dots)$ optimal ho, finish time se sort kiya hua; $g_{1}$ = greedy ka pehla pick (sabse pehle finish hone wala).

Claim/Swap. $o_{1}$ ko $g_{1}$ se replace karo $O^{'}$ banane ke liye.

Yeh step kyun? $g_{1}$ utna hi ya jaldi finish hota hai jitna $o_{1}$ ( $f_{g_{1}} \leq f_{o_{1}}$ , kyunki $g_{1}$ globally earliest finish wala hai). Toh jo $o_{1}$ ke khatam hone ke baad start hota tha woh $g_{1}$ ke khatam hone ke baad bhi start hota hai — feasibility preserved hai.

Worse kyun nahi? $O^{'}$ mein $O$ jitni same number of activities hain (humne ek ko ek se replace kiya). Toh $O^{'}$ bhi optimal hai, aur ab woh pehle pick par greedy se agree karta hai.

Induct karo remaining subproblem par ( $f_{g_{1}}$ ke baad start hone wali activities). Greedy har step par optimal rehti hai. ∎

Example 1 se contrast note karo: yahan swap equal cost deta hai (counting problem), wahan strict improvement diya. Dono valid exchange arguments hain.

Worked Example 3 — Huffman coding (sibling lemma)

Worked example "Two least frequent are siblings" exchange

Claim. Kisi optimal prefix tree mein, do sabse kam frequency wale symbols $x, y$ maximum depth par sibling leaves hain.

Setup. Optimal tree $T$ lo. $a, b$ do sabse gehri sibling leaves hon. WLOG $f (x) \leq f (y)$ aur $f (a) \leq f (b)$ , jahan $f (x), f (y)$ sabse chhoti do frequencies hain, toh $f (x) \leq f (a)$ , $f (y) \leq f (b)$ . Depths $d_{x} = depth (x)$ , etc. likho.

Swap. $x \leftrightarrow a$ aur $y \leftrightarrow b$ exchange karo — yeh do swaps hain, toh cost change do terms ka sum hai, ek per swap.

Worse kyun nahi? Cost $= \sum f (c) depth (c)$ . $x \leftrightarrow a$ swap se cost $(f (a) - f (x)) (d_{x} - d_{a})$ se change hoti hai, aur $y \leftrightarrow b$ swap se $(f (b) - f (y)) (d_{y} - d_{b})$ se. Total change hai $Δ = (f (a) - f (x)) (d_{x} - d_{a}) + (f (b) - f (y)) (d_{y} - d_{b}) .$ Yeh step kyun? Tumhe dono terms add karni hain — sirf ek swap account karna incomplete hoga.

Har term $\leq 0$ hai: pehle mein, $f (a) \geq f (x)$ jabki $a$ ek sabse gehri leaf hai toh $d_{a} \geq d_{x}$ , deta hai (non-neg) $\times$ (non-pos) $\leq 0$ ; doosra identical hai $f (b) \geq f (y)$ , $d_{b} \geq d_{y}$ ke saath. Isliye $Δ \leq 0$ — cost nahi badhti. ∎

Figure — Greedy — exchange argument proof technique

Steel-manning the mistakes

Recall Feynman: 12-saal ke bacche ko explain karo

Imagine karo ki bacchon ko line mein lagana hai — jo sabse jaldi kaam karta hai woh pehle. Main tumhe mera "hamesha-sबसे-jaldi-wala-aage" plan dikhata hoon. Tum bolte ho "lekin asli best plan alag ho sakta hai!" Toh main tumhara supposed best plan leta hoon, pehli jagah dhundhta hoon jahan woh mere se disagree karta hai, aur do bacchon ko swap karta hoon. Main prove karta hoon ki total waiting time swap ke baad nahi badhti. Main tab tak swapping karta rehta hoon jab tak tumhara plan bilkul mere jaisa na dikhe — aur kyunki maine kabhi ise worse nahi banaya, mera simple plan sab se best tha. Woh swapping trick hi exchange argument hai.

Active-recall flashcards

Exchange argument kya transform karta hai, aur kisme?

Kisi bhi optimal solution

O

ko, greedy ke solution

G

mein, swaps ki ek chain se jo kabhi cost nahi badhati.

Har swap ke baad ke TWO obligations kya hain?

(1) Swapped solution feasible rehta hai; (2) uski cost pehle se worse nahi hoti.

SPT proof mein, jab inversion

a

before

b

swap karo toh cost

(O) -

cost

(O^{'})

kya hota hai?

p_{a} - p_{b} > 0

(longer-before-shorter strictly worse hota hai) — unweighted

\sum C_{k}

ke liye.

Weighted completion time

\sum w_{k} C_{k}

ke liye, sahi greedy order kya hai?

Ratio

p_{k} / w_{k}

se sort karo (Smith's rule); SPT special case hai

w_{k} = 1

ke saath.

G

aur

O

ke beech PEHLE index par swap kyun karna chahiye jahan woh differ karte hain?

Matching prefix par induction karne ke liye aur guarantee karne ke liye ki swaps finitely many steps mein

G

tak pahunchein.

Counting problems (activity selection) mein swap ke baad kaisi inequality milti hai?

Equality (same number of activities) — tum dikhate ho ki ek optimal solution greedy se match karta hai, strict improvement nahi.

Ek aisi denomination set do jahan greedy coin change fail kare.

{1, 3, 4}

mein

6

banao: greedy =

4 + 1 + 1

(3 coins), optimal =

3 + 3

(2 coins).

Activity selection mein,

o_{1}

ko greedy ke

g_{1}

se replace karna feasibility kyun preserve karta hai?

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

, toh jo bhi activity

o_{1}

khatam hone ke baad compatible thi woh

g_{1}

khatam hone ke baad bhi compatible hai.

Exchange proof kaunsi telescoping inequality finish karti hai?

cost

(G) \leq

cost

(O) =

OPT, toh cost

(G) =

OPT.

Huffman ke sibling lemma mein, total cost change

\leq 0

kyun hai?

Yeh do swap terms ka SUM hai

(f (a) - f (x)) (d_{x} - d_{a}) + (f (b) - f (y)) (d_{y} - d_{b})

, har ek (non-neg)

\times

(non-pos) product hai.

Connections

Greedy Algorithms — general paradigm
Greedy-stays-ahead proof technique
Activity Selection Problem
Huffman Coding
Scheduling to minimise completion time
Smith's rule — weighted completion time
Matroids and the greedy theorem (algebraic reason ki exchange poori classes of problems ke liye kyun kaam karta hai)
Proof by contradiction aur Induction
Dynamic Programming (jab koi exchange argument exist nahi karta tab kya use karo)