Greedy — exchange argument proof technique: Foundations

3.7.3 · D1 · Coding › Algorithm Paradigms › Greedy — exchange argument proof technique

Yeh page exchange-argument note ka ground floor hai. Uss proof ki ek bhi line padhne se pehle, tumhe har woh symbol apna banana hoga jo woh tumpar fenkta hai. Hum har ek ko ek picture se build karte hain — koi bhi symbol yahan tab tak nahi aata jab tak tumne dekh nahi liya ki uska matlab kya hai.

0. Scene: hum aakhir mein kaun sa problem kar rahe hain?

Lagbhag har exchange proof ek scheduling ya choosing duniya mein rehta hai. Ek single machine socho — ek printer, ek CPU, ek busy insaan — jo ek waqt mein sirf ek task kar sakta hai. Tumhare paas jobs ka ek pile hai. Tumhe decide karna hai ki unhe kaunse order mein karo. Alag alag orders ka alag alag cost hota hai. Hum sabse sasta order chahte hain.

Ek greedy rule order decide karne ki ek simple recipe hai aage dekhe bina: har step pe, woh job chuno jo ek fixed criterion pe best score kare. Do greedy rules jo tumhe parent note mein milenge:

Shortest-Job-First (SPT): hamesha abhi tak na kiya gaya sabse chhota job pehle chalao.
Smallest-ratio-first (Smith's rule): hamesha woh job chalao jiska $p_{k} / w_{k}$ sabse chhota ho (yeh tab use hota hai jab jobs ke importance weights hon — §4 dekho).

Neeche sab kuch uss picture ke baare mein precisely baat karne ki vocabulary hai.

1. Ek job aur uski length $p_{k}$

Plain words: $p_{k}$ = "job number $k$ ko kitna waqt lagta hai."
Picture: Figure 1 mein har job ek coloured bar hai; bar ki width $p_{k}$ hai. Chauda bar = lamba job.
Yeh kyun chahiye: poora game jobs ko order karne ke baare mein hai, aur cost is baat pe depend karta hai ki har ek kitna lamba hai. Lengths ke bina optimise karne ke liye kuch nahi hai.

$p$ ke neeche latka chhota $k$ ek subscript hai — yeh multiplication nahi hai. $p_{k}$ ko "p-sub-k" padha jaata hai aur iska matlab sirf hai "job $k$ ka $p$ ." Toh $p_{3}$ job 3 ki length hai.

2. Completion time $C_{k}$

Plain words: "job $k$ done hone pe kitna baja hai?"
Picture: neeche.
Yeh kyun chahiye: woh cost jo hum minimise karte hain woh inhiin finish-times se bani hai. Yeh woh number hai jis baare mein poora topic sochta hai.

Picture ka key insight: kisi job ka completion time usse pehle ya uske order mein barabar aane wali har job ki lengths ka sum hota hai. Agar order hai job A (length 3), phir job B (length 2), toh: $C_{A} = 3, C_{B} = 3 + 2 = 5.$ Job B ko A ke finish hone ka wait karna pada — woh waiting $C_{B}$ mein baka hai. Isi liye order matter karta hai.

3. Sum symbol $\sum$

Plain words: $\sum_{k = 1}^{n} C_{k} = C_{1} + C_{2} + C_{3} + \dots + C_{n}$ — har job ke liye ek term, koi job chhoot nahi.
Picture: har job ki finish-time ko stack karo aur heights total karo.
Yeh kyun chahiye: humara objective — woh cheez jo hum minimise karte hain — hai total completion time $\sum_{k = 1}^{n} C_{k}$ . Yeh jobs ko jaldi finish karne ko reward karta hai, kyunki jaldi finish karna ek chhota number hai jo pile mein add hota hai.

4. Weight $w_{k}$ aur ratio $p_{k} / w_{k}$

Plain words: har job ke liye importance dial.
Picture: sunset figure mein, socho har bar ki ek brightness bhi hai — brighter = zyada important = zyada weight.
Yeh kyun chahiye: general objective hai weighted total $\sum_{k = 1}^{n} w_{k} C_{k}$ : ek important job late finish hona bahut cost karta hai, ek unimportant ek late finish hona thoda cost karta hai. Jab sab $w_{k} = 1$ hote hain toh yeh wapas plain $\sum_{k = 1}^{n} C_{k}$ ban jaata hai.

Parent note ke mistake-box mein ratio $\frac{p _{k}}{w _{k}}$ ("length divided by importance") use hota hai. Chhota ratio = chhota aur important = pehle karo. Yeh Smith's rule hai (dekho Smith's rule — weighted completion time).

5. Jobs ki sankhya $n$ , aur do solutions $G$ (greedy) aur $O$ (optimal)

Plain words: $n$ = "kitne jobs hain"; $G$ = "greedy kya karta hai"; $O$ = "ek true champion answer." Dono lists mein exactly wohi $n$ jobs hain — sirf order differ karta hai.
Picture: unhi coloured bars ki do rows, possibly alag left-to-right orders mein.
Yeh kyun chahiye: poora proof in do lists ko position by position compare karta hai. Parentheses $(g_{1}, \dots, g_{n})$ sirf ek ordered list hai — $g_{1}$ pehli cheez hai jo ki jaati hai, $g_{n}$ aakhri. Subscript ek position hai, koi job number nahi.

6. Cost aur OPT

Plain words: $cost (\cdot)$ = ek machine jo koi bhi ordering khaati hai aur uska price tag ugalti hai; $OPT$ = sabse chhota price tag jo exist karta hai.
Yeh kyun chahiye: "optimal" define hota hai $cost (O) = OPT$ se. Proof ka punchline hai $cost (G) = OPT$ , yaani greedy best price hit karta hai.

7. Inequality $\leq$ aur "no worse"

Har exchange proof ka engine ek inequality hai: $cost (O^{'}) \leq cost (O)$ .

Picture: ek see-saw jo swap ke baad neeche jaata hai ya level rehta hai, kabhi upar nahi.

8. Swap (exchange) khud, aur ek inversion

Picture: neeche — do bars pakdo, arrows cross karo, har ek ko dusre ki jagah rakho.
Yeh kyun chahiye: proof baar baar inversions ko swapping karke remove karta hai. Har swap $O$ aur $G$ ke beech ek disagreement fix karta hai.

Kyunki sirf swapped pair move karta hai, sirf unki completion times change hoti hain — har doosra job same clock time pe start aur end hota hai. Isi se cost change compute karna easy ho jaata hai (sirf do terms).

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

Plain words: woh sabse pehla spot dhundho jahaan dono lists differ karti hain; greedy ki choice ko $O$ mein jahaan bhi chhupa ho wahan se upar uss spot pe le aao.
Yeh kyun first difference: taki pehle se match karne wala hissa matched rahe. Isse hum steadily $G$ ki taraf progress karte hain aur guarantee karte hain ki process ruk jayegi (finitely many disagreements, har swap ek ko khatam karta hai). Neeche Induction idea dekho.

10. Telescoping aur final chain

Plain words: orderings ki ek domino line, har ek pichle se no worse, ek optimal $O$ pe start hokar exactly $G$ pe end hoti hai $m$ steps ke baad.
Picture: ek staircase jo kabhi sirf neeche ya flat jaata hai.

Intuition Kyun kaafi saare "

$\leq$ " steps chain karke ek inequality mein collapse ho jaate hain Humne prove kiya ki har single step no worse hai: $cost (O_{1}) \leq cost (O_{0})$ , aur $cost (O_{2}) \leq cost (O_{1})$ , aur aage bhi $cost (O_{m}) \leq cost (O_{m - 1})$ tak. Ab inhe ek girte hue staircase ki tarah padho: agar step 1 start se no higher hai, aur step 2 step 1 se no higher hai, ... toh aakhri step bilkul pehle se no higher hai. Formally tum har inequality ko agale mein substitute karte ho — $cost (O_{2}) \leq cost (O_{1}) \leq cost (O_{0})$ — aur middle terms drop ho jaate hain ("telescope"), sirf yeh bachta hai $cost (O_{m}) \leq cost (O_{0}), i.e. cost (G) \leq cost (O) = OPT .$ Kyunki kuch bhi $OPT$ ko beat nahi kar sakta (yeh definition se sabse chhota cost hai), $cost (G)$ isse neeche bhi nahi ja sakta, toh $cost (G) = OPT$ : greedy optimal hai. Yeh chaining ek inductive argument hai, aur naturally contradiction ke saath pair karta hai.

11. Do proof flavours jo tumhe milenge

Dono greedy algorithms ke umbrella ke neeche rehte hain, aur dono (usually heavier) dynamic programming proofs ke alternatives hain.

Prerequisite map

Equipment checklist

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

Ek greedy rule kya hai, ek line mein?

Ek recipe jo har step pe ek fixed criterion se best-scoring choice pick karti hai, bina aage dekhe (jaise shortest-job-first).

p_{k}

mein subscript ka kya matlab hai — kya yeh multiplication hai?

Nahi — yeh hai "job

k

p

", padha jaata hai "p-sub-k". Multiplication nahi.

Kisi job ka completion time

C_{k}

kaise compute karte hain?

Running order mein us job tak aur us job ko include karte hue har job ki lengths ka sum karo.

\sum_{k = 1}^{n} C_{k}

kya represent karta hai, aur range kya hai?

C_{1} + C_{2} + \dots + C_{n}

— sab

n

jobs pe summed, koi chhoot nahi.

Jab jobs ke importance weights hon toh objective kya hai?

Weighted total

\sum_{k = 1}^{n} w_{k} C_{k}

; ratio

p_{k} / w_{k}

ke hisaab se sort karo (Smith's rule).

n

kya hai?

Schedule karne ke liye jobs ki total sankhya;

G

aur

O

dono unhe sab list karte hain.

G

aur

O

kya hain — numbers ya kuch aur?

Poori orderings (

n

jobs ki sequences); hum unki costs compare karte hain, jo numbers hain.

cost (\cdot)

mein dot ka kya matlab hai?

Ek placeholder — koi bhi ordering brackets ke andar daalo uski price paane ke liye.

OPT

define karo.

Sabse chhota cost jo koi bhi ordering possibly achieve kar sakti hai.

Exchange proofs

<

ki jagah

\leq

kyun use karte hain?

Kyunki ek swap tie (equal cost) ya improve kar sakta hai; "no worse" exactly

\leq

hai.

Ek inversion kya hai (unweighted aur weighted)?

Do adjacent jobs greedy rule ke liye galat order mein: longer-before-shorter (unweighted), ya larger-

p_{k} / w_{k}

-before-smaller (weighted).

Ek single swap ke baad kiske completion times change hote hain?

Sirf do swapped jobs ke; baaqi sab same start aur finish time rakhte hain.

Hum first difference

i

pe kyun swap karte hain?

Already-matching prefix ko matched rakhne ke liye aur

G

ki taraf finite progress guarantee karne ke liye.

Telescoping chain mein

O_{i}

aur

m

kya hain?

O_{i}

i

swaps ke baad ki ordering hai;

m

G

tak pahunchne ke liye needed finite swaps ki sankhya hai (

m \leq n

Kaafi saare "

\leq

" steps chain karna ek inequality kyun deta hai?

Har step pichle se no worse hai, toh unhe substitute karne se collapse (telescope) hota hai

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

mein.

Aage: parent note pe wapas jaao aur 5-step skeleton padho — wahan ka har symbol ab tumhara hai.