Approximation algorithms — approximation ratio, examples

4.6.29 · Coding › Theory of Computation

WHAT is an approximation ratio?

Example 1 — Vertex Cover (2-approximation)

Algorithm (Maximal Matching based):

$C \leftarrow \emptyset$ .
Jab tak koi uncovered edge $(u, v)$ ho: dono $u$ aur $v$ ko $C$ mein daalo, saari edges jo $u$ ya $v$ ko touch karti hain unhe delete karo.
$C$ return karo.

Worked example Yeh ratio 2 kyun deta hai? (Scratch se derivation)

Woh edges $(u, v)$ jo humne step 2 mein choose kiye woh ek matching $M$ banate hain (koi do vertex share nahi karte — jab hum $(u, v)$ choose karte hain toh unki saari edges delete kar dete hain).

Yeh step kyun? Do facts (yahaan lower bound $LB = ∣ M ∣$ hai):

Lower bound on OPT: kisi bhi vertex cover ko $M$ ki har edge cover karni padti hai. Kyunki $M$ ki edges disjoint hain, tumhe kam se kam ek distinct vertex per matched edge chahiye. Isliye $LB = ∣ M ∣ \leq OPT$ .
Upper bound on ALG: humne exactly 2 vertices per matched edge daale, isliye $ALG = 2∣ M ∣ = 2 LB$ .

Standard pattern mein combine karo: $ALG = 2∣ M ∣ = 2 LB \leq 2 \cdot OPT .$ Isliye $ρ = 2$ . ✅ Yeh ek 2-approximation hai, aur notice karo ki humne OPT kabhi compute nahi kiya — sirf lower bound $∣ M ∣$ .

Figure — Approximation algorithms — approximation ratio, examples

Example 2 — Metric TSP (2-approximation via MST)

Algorithm (Double-tree):

Ek Minimum Spanning Tree $T$ banao.
$T$ ka DFS/Euler walk karo (har edge twice) → walk cost $= 2 \cdot cost (T)$ .
Repeated cities ko shortcut karo (already-visited ko skip karo) → ek valid tour.

Example 3 — Load Balancing (Greedy, 2-approximation)

$n$ jobs ko $m$ machines pe assign karo, makespan (max load) minimize karo.

Common mistake Common errors ko steel-man karna

Mistake A: "2-approximation ka matlab main 50% time sahi hoon / 50% galat hoon." Kyun sahi lagta hai: "2" ek percentage jaisa lagta hai. Fix: iska matlab cost $\leq 2 \times$ optimal worst case mein, hamesha, deterministically — yeh probability nahi hai. Usually tum $2 \times$ se kaafi close hote ho.

Mistake B: "Ratio prove karne ke liye mujhe OPT pata hona chahiye." Kyun sahi lagta hai: ratio mein literally OPT hai. Fix: tum ek lower bound $LB \leq OPT$ (matching size, MST cost, average load) se compare karte ho: dikhao $ALG \leq ρ LB$ , phir $LB \leq OPT$ finish karta hai. OPT kabhi compute nahi hota.

Mistake C: MST-double-tree ko non-metric TSP par use karna. Kyun sahi lagta hai: algorithm theek se run hota hai. Fix: shortcutting ke liye triangle inequality chahiye; uske bina bound collapse ho jaata hai, aur general TSP mein koi constant-factor approximation nahi hoti (unless P=NP).

Mistake D: Maximization ke liye likhna $ALG / OPT \leq ρ$ . Fix: maximization ratios neeche se bound karte hain: $ALG \geq ρ OPT$ jahan $ρ \leq 1$ .

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho ek backpack ko perfect tarike se pack karna forever lagg jaata hai. Iske bajaye tum ek quick rule of thumb use karte ho. Tum exactly nahi bata sakte ki perfect packing kitni achi hai — lekin tum ek floor dhundh sakte ho: "perfect packing ko kam se kam itni space chahiye." Phir tum dikhate ho "mera quick tarika us floor se zyada se zyada double use karta hai." Kyunki perfect answer bhi floor ke upar hai, mera quick answer perfect wale se zyada se zyada double hai. Woh promise — perfect answer jaane bina — approximation ratio hai.

Connections

NP-completeness — kyun hum approximate karte hain.
Vertex Cover · Maximum Matching — 2-approx lower bound.
Minimum Spanning Tree — Metric TSP ka bound.
Greedy Algorithms — load balancing.
PTAS and FPTAS · Inapproximability / PCP theorem.
Triangle Inequality — shortcutting enable karta hai.

Minimization problem ke liye approximation ratio kya hota hai?

Worst-case ratio ALG/OPT ≤ ρ (ρ≥1) saare inputs par; ρ=1 exact hai.

Hum OPT jaane bina ratios kyun prove kar sakte hain?

Ek lower bound LB ≤ OPT dhundho (matching size, MST cost, average load), prove karo ALG ≤ ρ·LB, phir ALG ≤ ρ·LB ≤ ρ·OPT.

Vertex Cover 2-approx: algorithm kya hai?

Baar baar koi bhi uncovered edge chuno, DONO endpoints ko cover mein daalo, incident edges remove karo.

Vertex Cover proof mein OPT ≥ |M| kyun hai?

Choose ki gayi edges ek matching banati hain; har disjoint edge ko ≥1 distinct cover vertex chahiye, isliye OPT ≥ matching size.

Vertex Cover mein ALG = 2|M| kyun hai?

Hum exactly 2 vertices per matched edge dalete hain.

Metric TSP double-tree: OPT par lower bound?

Optimal tour se ek edge hatao toh spanning tree milta hai, isliye cost(MST) ≤ OPT.

Shortcutting tour cost kyun nahi badhata?

Triangle inequality: ek city skip karna (a→c instead of a→b→c) ≤ detour cost hai.

Load balancing greedy ratio aur kyun?

2; kyunki OPT ≥ average load aur OPT ≥ max job size, aur L ≤ (L−t_j)+t_j ≤ 2·OPT.

PTAS aur FPTAS mein kya farq hai?

Dono (1+ε)-approx dete hain; FPTAS n AND 1/ε mein polynomial time mein chalta hai, PTAS sirf n mein (1/ε mein exponential ho sakta hai). Har FPTAS ek PTAS hai.

Kya general (non-metric) TSP mein constant-factor approximation hai?

Nahi (unless P=NP).

"2-approximation" ke baare mein common myth?

Yeh probability/percentage NAHI hai; yeh deterministic worst-case bound hai: ALG ≤ 2·OPT hamesha.