Approximation algorithms — approximation ratio, examples: Worked examples

Before anything, three symbols must be earned — the parent note used $ρ$ and $M$ freely, but on this page we define them from zero.

The scenario matrix

Every approximation question you'll meet lives in one of these cells. The worked examples below are each tagged with the cell they cover, so together they fill the whole grid.

#	Cell (case class)	What makes it special	Covered by
C1	Trivial / zero input — empty graph, one job, no edges	OPT $= 0$ ; ratio is $0/0$ — a division trap	Ex 1
C2	Loose ratio — algorithm far better than its guarantee	$ALG / OPT ≪ 2$ ; guarantee is not equality	Ex 2b (loose); Ex 2 (still tight)
C3	Tight ratio — worst case, $ALG / OPT$ equals 2	ratio equals $ρ$ ; proves the bound can't improve	Ex 3, Ex 5
C4	Metric geometry — triangle inequality active	shortcutting saves cost	Ex 4
C5	Non-metric trap — triangle inequality broken	bound collapses; algorithm may be arbitrarily bad	Ex 6
C6	Two-lower-bound problem — load balancing	must combine average + max	Ex 7
C7	Real-world word problem — jobs, servers, dressed-up numbers	translate words → makespan	Ex 8
C8	Exam twist — max vs min convention, PTAS reasoning	sign of the ratio flips	Ex 9

Two quick reminders of the value-notation before we start (earned, not assumed):

The figure below is the mental image behind every example on this page — keep glancing back at it. The yellow dot is the wall $LB$ we can compute, the pink dot is the hidden OPT we can't, and the blue dot is where our algorithm lands. The blue arrow (" $ALG \leq 2 \cdot LB$ ", the $ALG / LB$ ratio) is the only thing we prove directly; the yellow arrow (" $LB \leq OPT$ ") is free.

Figure — Approximation algorithms — approximation ratio, examples

C1 — The zero / degenerate input

Worked example Ex 1 — Vertex Cover on an edgeless graph (cell C1)

Statement. Graph $G$ has $4$ vertices ${a, b, c, d}$ and no edges. Run the maximal-matching Vertex Cover algorithm. What is $ALG$ , $OPT$ , and the ratio?

Forecast: Guess before reading. Many people say "the ratio is 2, so ALG = 2·OPT". What happens when OPT is $0$ ?

Run the algorithm. There are no uncovered edges, so the while loop never runs. $C = \emptyset$ , hence $ALG = 0$ . The maximal matching is $M = \emptyset$ , $∣ M ∣ = 0$ . Why this step? The algorithm only adds vertices when it finds an uncovered edge. No edges ⇒ nothing to cover ⇒ empty cover is valid.
Find OPT. An empty set covers all zero edges, so $OPT = 0$ . Why this step? We need OPT to even talk about a ratio.
The ratio. $\frac{ALG}{OPT} = \frac{0}{0}$ — undefined. The guarantee is stated as $ALG \leq ρ \cdot OPT = 2 \cdot OPT$ , i.e. $0 \leq 2 \cdot 0 = 0$ . True. Why this step? The inequality form $ALG \leq ρ \cdot OPT$ survives the degenerate case; the fraction form $ALG / OPT$ does not.

Verify: $ALG = 0 \leq 2 \cdot OPT = 0$ ✓. The guarantee holds as an inequality, and this is exactly why textbooks write $ALG \leq ρ OPT$ rather than the fraction — the fraction dies at OPT $= 0$ .

C2 — When the algorithm is much better than its promise

To see a genuinely loose $ALG / OPT$ (strictly below 2) we cannot use a graph where every edge shares one vertex — those force ties at 2. We need a graph where OPT exceeds the matching size $∣ M ∣$ .

Worked example Ex 2 — Vertex Cover on a triangle-plus-tail (cell C2, but still tight) (cell C2)

Statement. Graph $G$ : a triangle $a, b, c$ (edges $ab, b c, c a$ ) with an extra pendant leaf $d$ attached to $c$ (edge $c d$ ). So edges are ${ab, b c, c a, c d}$ . Run the matching-based 2-approx, always picking the lowest-labelled uncovered edge first.

Forecast: OPT for a triangle already needs 2 vertices; the tail may be covered "for free" by a vertex already chosen. Guess: does $ALG / OPT$ come in below 2 this time?

Run the algorithm. Lowest edge is $ab$ . Add $a, b$ ; delete edges touching $a$ or $b$ : that removes $ab, b c, c a$ . Remaining edge: $c d$ . Add $c, d$ ; remove $c d$ . Loop ends. $ALG = ∣ {a, b, c, d} ∣ = 4$ . Why this step? The matching found is $M = {ab, c d}$ — two disjoint edges — so the algorithm adds $2 \times 2 = 4$ vertices.
Find OPT. Try ${b, c}$ : edge $ab$ has $b$ ✓, $b c$ has $b$ ✓, $c a$ has $c$ ✓, $c d$ has $c$ ✓. All four edges covered by 2 vertices. Can 1 vertex work? No — the triangle alone needs $\geq 2$ . So $OPT = 2$ . Why this step? One clever vertex ( $c$ ) sits on both the triangle and the tail, covering three edges at once — that's what pulls OPT down toward $∣ M ∣$ .
Ratio. $\frac{ALG}{OPT} = \frac{4}{2} = 2$ — hmm, still exactly 2 here because the matching was disjoint and $OPT = ∣ M ∣$ . So even this is tight. Why this step? Whenever $OPT = ∣ M ∣$ , the performance ratio is exactly $\frac{2∣ M ∣}{OPT} = 2$ . To break below 2 we must make $OPT > ∣ M ∣$ .

Verify: $ALG = 4 \leq 2 \cdot OPT = 4$ ✓, ratio $2$ . This teaches the key fact: the performance ratio is $\frac{2∣ M ∣}{OPT}$ , and it is $< 2$ precisely when $OPT > ∣ M ∣$ . See Ex 2b for a graph where that finally happens.

Worked example Ex 2b — An odd cycle

$C_{5}$ : ratio strictly below 2 (cell C2, truly loose) Statement. A 5-cycle $v_{1} v_{2} v_{3} v_{4} v_{5} v_{1}$ (5 edges). Run the algorithm, picking $v_{1} v_{2}$ then the lowest remaining edge.

Forecast: An odd cycle can't be perfectly matched. Guess how many matching edges the algorithm finds, and whether OPT exceeds it.

Run the algorithm. Pick $v_{1} v_{2}$ : add $v_{1}, v_{2}$ ; delete edges touching them: $v_{5} v_{1}, v_{1} v_{2}, v_{2} v_{3}$ gone. Remaining edges: $v_{3} v_{4}, v_{4} v_{5}$ . Pick $v_{3} v_{4}$ : add $v_{3}, v_{4}$ ; delete $v_{3} v_{4}$ and $v_{4} v_{5}$ . Loop ends. $ALG = ∣ {v_{1}, v_{2}, v_{3}, v_{4}} ∣ = 4$ . Matching $M = {v_{1} v_{2}, v_{3} v_{4}}$ , so $∣ M ∣ = 2$ . Why this step? The odd cycle leaves $v_{5}$ unmatched — the matching cannot cover all 5 edges with disjoint pairs.
Find OPT. A cover of $C_{5}$ needs $\geq 3$ vertices (an odd cycle of $n$ vertices needs $⌈ n /2 ⌉ = 3$ ). E.g. ${v_{1}, v_{3}, v_{4}}$ : check $v_{1} v_{2}$ ✓( $v_{1}$ ), $v_{2} v_{3}$ ✓( $v_{3}$ ), $v_{3} v_{4}$ ✓, $v_{4} v_{5}$ ✓( $v_{4}$ ), $v_{5} v_{1}$ ✓( $v_{1}$ ). So $OPT = 3$ . Why this step? Odd cycles force OPT strictly above $∣ M ∣$ — exactly the condition for a loose ratio.
Ratio. $\frac{ALG}{OPT} = \frac{4}{3} \approx 1.33 < 2$ . Genuinely loose! Why this step? Here $OPT = 3 > ∣ M ∣ = 2$ , so $\frac{2∣ M ∣}{OPT} = \frac{4}{3} < 2$ — the algorithm beat its own guarantee.

Verify: $ALG = 4 \leq 2 \cdot OPT = 6$ ✓, performance ratio $= 4/3 \approx 1.33$ . Insight earned: the guarantee " $\leq 2$ " is a worst-case ceiling; on real graphs like odd cycles you routinely land well under it.

C3 — The tight case (worst possible)

The figure contrasts the two extremes referenced in the steps below. Left panel = Graph A of Ex 3 (triangle): the blue vertices $a, b$ are the cover; $OPT = ALG = 2$ , ratio $1$ (loose). Right panel = Graph B of Ex 3 (three disjoint pink edges): the algorithm picks all three (blue "pick" endpoints), doubling a matching that OPT covers with one vertex per edge; ratio $2$ (tight). Read the two panels as "best case vs adversary's best weapon".

Worked example Ex 3 — Triangle (loose) vs disjoint edges (tight) (cell C3)

Statement. Compare two graphs: (A) A single triangle $a, b, c$ (edges $ab, b c, c a$ ). (B) A perfect matching of $2 k$ vertices: $k$ disjoint edges $e_{1}, \dots, e_{k}$ with no shared vertices.

Forecast: In which one does $ALG / OPT$ equal exactly $2$ ?

Graph A (triangle) — see the LEFT panel of the figure above:

Pick edge $(a, b)$ , add $a, b$ , delete edges touching them: $ab, b c, c a$ all touch $a$ or $b$ → all gone. $M = {ab}$ , $ALG = 2$ . Why this step? Running the algorithm gives us $ALG$ ; a single matched edge already covers the whole triangle.
OPT: you need $\geq 2$ vertices (one vertex leaves one edge uncovered). E.g. ${a, b}$ covers all three edges. $OPT = 2$ . Why this step? We must know OPT to form the performance ratio $ALG / OPT$ .
Ratio $\frac{ALG}{OPT} = \frac{2}{2} = 1$ . Loose — the guarantee said " $\leq 2$ " but we hit 1 (exact). Why this step? Odd cycles (a triangle is $C_{3}$ ) force $OPT$ up to match ALG, so the ratio looks great here.

Graph B ( $k$ disjoint edges, use $k = 3$ , so 6 vertices) — see the RIGHT panel:

Each edge is disjoint, so the algorithm picks all $k$ of them into $M$ , adding 2 vertices each: $M = {e_{1}, e_{2}, e_{3}}$ , $ALG = 2 k = 6$ . Why this step? Simulating the algorithm on disjoint edges reveals it grabs every edge — that fixes $ALG$ .
OPT: each disjoint edge needs its own covering vertex, and one endpoint per edge suffices: $OPT = k = 3$ . Why this step? OPT is required to compute the performance ratio, and disjointness forces one vertex per edge.
Ratio $\frac{ALG}{OPT} = \frac{2 k}{k} = 2$ . Tight — the performance ratio equals $ρ$ . Why this step? Disjoint edges are the adversary's best weapon: $∣ M ∣ = OPT$ , but the algorithm doubles it.

Verify: A: $2 \leq 2 \cdot 2$ ✓, ratio $1$ . B: $6 \leq 2 \cdot 3 = 6$ ✓, ratio $2$ . The disjoint-edge family proves the 2-approximation cannot be improved to any $ρ < 2$ for this algorithm.

Worked example Ex 5 — Metric TSP whose double-tree tour hits ratio 2 against OPT (cell C3)

Statement. We want a metric where the double-tree tour is a full factor 2 above OPT, not just above the LB. Take $n$ cities placed as a "star" so the MST is a path but OPT is a short cycle. Concretely: $2 k + 1$ cities where $k$ leaf-pairs hang off a spine so that $cost (T)$ and $OPT$ are almost equal, and doubling truly doubles. Use the clean $k$ -city cycle metric: $n$ cities equally spaced on a circle, unit distance between neighbours, and metric distances = shortest-path-along-the-cycle. Take $n = 4$ on a cycle: neighbour distance $1$ , opposite distance $2$ (metric ✓ since $2 \leq 1 + 1$ ).

Forecast: MST of a 4-cycle metric is a path of 3 unit edges. Double, then shortcut. Guess whether the tour is close to $2 \cdot OPT$ .

MST. The 4 cities $c_{1} c_{2} c_{3} c_{4}$ on the cycle: cheapest tree is the path $c_{1} c_{2} c_{3} c_{4}$ , cost $cost (T) = 1 + 1 + 1 = 3 = LB$ . Why this step? MST cost is the lower bound $LB$ ; a 3-edge path connects all 4 cities cheapest.
Double walk. $2 \cdot 3 = 6$ : walk $c_{1} c_{2} c_{3} c_{4} c_{3} c_{2} c_{1}$ . Why this step? Doubling every tree edge makes an Eulerian closed walk touching all cities, cost $2 \cdot cost (T)$ .
Shortcut — the adversarial part. Shortcut the return: after $c_{4}$ we jump straight back to $c_{1}$ . In this cycle metric $d (c_{1}, c_{4}) = 1$ (they are neighbours on the circle!). Tour $c_{1} c_{2} c_{3} c_{4} c_{1} = 1 + 1 + 1 + 1 = 4$ . Why this step? Triangle inequality guarantees shortcutting never raises cost; here it gives a clean 4-edge tour.
OPT. The optimal tour of the 4-cycle metric is the cycle itself, $c_{1} c_{2} c_{3} c_{4} c_{1} = 4$ . So $OPT = 4$ ; performance ratio $= 4/4 = 1$ . Why this step? We need OPT to form $ALG / OPT$ — and here the tour is optimal.

Verify: $ALG = 4 \leq 2 \cdot LB = 6$ ✓, but the performance ratio is only $1$ , not $2$ . This exposes an important subtlety flagged in the matrix: small metrics make the $ALG \leq 2 \cdot LB$ bound tight (here $4$ vs $6$ ? no — $4 < 6$ , so not even that). To get $ALG / OPT \to 2$ you need the family below, not one small graph.

The genuine worst case (a family, not a fixed graph). Put $n$ cities so the MST is a path of unit edges of cost $n - 1$ , and OPT $= n$ (path plus one long closing edge $\approx 1$ ). Double-tree yields $ALG = 2 (n - 1)$ ; if the metric forces the shortcut tour to still cost $\approx 2 (n - 1)$ while $OPT = n$ , then $\frac{ALG}{OPT} = \frac{2 ( n - 1 )}{n} n \to \infty 2.$ Why a family? A single small graph cannot reach the limit; the ratio $2$ is an asymptotic worst case. This is precisely why the guarantee is stated as " $\leq 2$ ", tight only in the limit — and why Christofides' $3/2$ is a real improvement.

C4 — Metric TSP, triangle inequality doing real work

In this figure (matching Ex 4) the yellow edges are the MST (three sides of the unit square, cost $3$ ), the pink dotted edge is the unused diagonal ( $\approx 1.414$ — too costly), and the blue dashed edge is the shortcut $P_{4} \to P_{1}$ that closes the tour in step 3. Watch how shortcutting turns the doubled walk into the clean 4-edge perimeter.

Worked example Ex 4 — Four cities on a square, double-tree tour (cell C4)

Statement. Four cities at corners of a unit square: $P_{1} = (0, 0)$ , $P_{2} = (1, 0)$ , $P_{3} = (1, 1)$ , $P_{4} = (0, 1)$ . Straight-line (Euclidean) distances — these obey the Triangle Inequality. Side length $1$ , diagonal $2 \approx 1.414$ . Run double-tree.

Forecast: OPT is clearly the square's perimeter. Will double-tree find it, or will shortcutting leave us above it?

Build an MST. Cheapest tree connecting all four: three sides, e.g. $P_{1} P_{2}, P_{2} P_{3}, P_{3} P_{4}$ , cost $= 1 + 1 + 1 = 3$ . (Any 3 sides, avoiding the pricey diagonal, cost 3.) Why this step? MST cost is our lower bound $LB = 3$ .
Euler / double walk. Walk each tree edge twice: cost $= 2 \cdot 3 = 6$ . The walk revisits vertices. Why this step? Doubling every edge makes an Eulerian closed walk that touches all cities, giving a cost of exactly $2 \cdot cost (T)$ to shortcut from.
Shortcut (blue dashed edge in figure). The doubled walk is $P_{1} \to P_{2} \to P_{3} \to P_{4} \to P_{3} \to P_{2} \to P_{1}$ . Skip already-visited cities: the tour becomes $P_{1} \to P_{2} \to P_{3} \to P_{4} \to P_{1}$ . Cost $= 1 + 1 + 1 + 1 = 4$ . Why this step? By triangle inequality, replacing $P_{4} \to P_{3} \to P_{2} \to P_{1}$ by the direct $P_{4} \to P_{1}$ never raises cost — it drops from $3$ to $1$ .
Find OPT. The optimal tour is the perimeter $P_{1} P_{2} P_{3} P_{4} P_{1} = 4$ . Why this step? We need OPT to report the true performance ratio $ALG / OPT$ , not just the LB bound.

Verify: $ALG = 4 \leq 2 \cdot LB = 6$ and $LB = 3 \leq OPT = 4$ ✓. Performance ratio $ALG / OPT = 4/4 = 1$ : shortcutting was so effective we hit the optimum. The diagonal $2$ never entered the tour — good, because $22 \approx 2.83 > 2$ per crossing.

C5 — The non-metric trap

Worked example Ex 6 — Same algorithm, triangle inequality broken (cell C5)

Statement. Three cities with distances $d (1, 2) = 1$ , $d (2, 3) = 1$ , $d (1, 3) = 100$ . Check: is $d (1, 3) \leq d (1, 2) + d (2, 3)$ ? That's $100 \leq 2$ — false. Triangle inequality is violated. Run double-tree.

Forecast: The parent note warns shortcutting needs the triangle inequality. What goes wrong here?

MST. Cheapest tree: edges $(1, 2)$ and $(2, 3)$ , cost $= 1 + 1 = 2 = LB$ . Why this step? Avoid the huge $100$ edge; connect $1 - 2 - 3$ so $LB = cost (T) = 2$ .
Double walk. $2 \cdot 2 = 4$ : walk $1 \to 2 \to 3 \to 2 \to 1$ . Why this step? Doubling gives the Eulerian walk of cost $2 \cdot cost (T)$ that we would normally shortcut down from.
Shortcut. To close the tour we must return $3 \to 1$ directly, cost $100$ . Tour $1 \to 2 \to 3 \to 1 = 1 + 1 + 100 = 102$ . Why this step? Shortcutting forced the giant direct edge — with no triangle inequality, "skipping" made things worse, not better.
OPT. Any tour of 3 cities uses all three edges once: $1 + 1 + 100 = 102$ . So $OPT = 102$ here too — but only because every tour is forced through the 100-edge. Why this step? We need OPT to expose that the bound $ALG \leq 2 \cdot LB$ — not the true optimum — is what breaks.

Verify: $ALG = 102$ . Guarantee claim would be $ALG \leq 2 \cdot LB = 4$ — FALSE ( $102 \neq \leq 4$ ). The 2-approximation breaks: it only ever held because step 3 relied on triangle inequality. General (non-metric) TSP has no constant-factor approximation unless $P = NP$ (Inapproximability / PCP theorem).

C6 & C7 — Load balancing: two lower bounds, and a real job

The bar chart shows the greedy result of Ex 7: stacked jobs on two machines, the blue dashed line marking the achieved makespan (ALG $= 7$ ) and the yellow dotted line marking OPT $= 6$ (which equals the average-load lower bound here). The gap between the two lines is the approximation slack.

Worked example Ex 7 — Greedy makespan, both bounds needed (cell C6)

Statement. $m = 2$ machines, jobs with sizes $[3, 3, 2, 2, 2]$ . Greedy assigns each job to the currently least-loaded machine (ties → machine 1). Find makespan.

Forecast: Total work $= 12$ , so a perfect split is $6$ each. Will greedy find $6$ ?

Simulate greedy.
- Job 3 → M1 (loads: 3, 0)
- Job 3 → M2 (loads: 3, 3)
- Job 2 → M1 (tie → M1) (loads: 5, 3)
- Job 2 → M2 (loads: 5, 5)
- Job 2 → M1 (tie → M1) (loads: 7, 5) Makespan $= max (7, 5) = 7 = ALG$ . Why this step? Greedy is defined by the least-loaded rule; simulate it exactly to get $ALG$ .
Lower bound 1 — average. $OPT \geq \frac{1}{m} \sum t_{k} = \frac{12}{2} = 6$ . Why this step? Someone must carry at least the average load — our first $LB$ .
Lower bound 2 — biggest job. $OPT \geq max_{k} t_{k} = 3$ . Why this step? A single job of size 3 lands on one machine wholly — a second, independent $LB$ .
Combine. $OPT \geq max (6, 3) = 6$ . The true optimum: split $[3, 3]$ vs $[2, 2, 2]$ → loads $6$ and $6$ , so $OPT = 6$ . Why this step? Two lower bounds give the tightest floor; an explicit schedule confirms OPT equals it.

Verify: $ALG = 7 \leq 2 \cdot OPT = 12$ ✓ and performance ratio $= 7/6 \approx 1.17$ . The proof's inequality $L = (L - t_{j}) + t_{j} \leq OPT + OPT$ : here $t_{j} = 2$ (last job on M1), $L - t_{j} = 5 \leq 6$ ✓, so $L \leq 6 + 2 = 8$ , consistent with the actual $7$ .

Worked example Ex 8 — Word problem: web requests on servers (cell C7)

Statement. A load balancer has $m = 3$ servers. Five requests arrive with CPU-seconds $[5, 4, 3, 2, 2]$ (total $16$ ). Requests are routed greedily to the least-busy server. What is the finishing time (makespan), and how close to optimal is it guaranteed to be?

Forecast: $16/3 \approx 5.33$ , so a great schedule finishes around $6$ . Can greedy be twice that?

Simulate (ties → lowest-index server):
- 5 → S1 (5, 0, 0)
- 4 → S2 (5, 4, 0)
- 3 → S3 (5, 4, 3)
- 2 → S3 (least loaded is S3 at 3) (5, 4, 5)
- 2 → S2 (least loaded is S2 at 4) (5, 6, 5) Makespan $= max (5, 6, 5) = 6 = ALG$ . Why this step? Translate "route to least-busy server" into the greedy rule; run it to get $ALG$ .
Lower bounds. Average $= 16/3 \approx 5.33$ ; biggest job $= 5$ . Loads are made of whole jobs, so a machine's load is an integer — it cannot equal $5.33$ . The smallest integer $\geq 5.33$ is $6$ , hence $OPT \geq 6$ (and $\geq max_{k} t_{k} = 5$ , weaker here). Why this step? The average bound gives $5.33$ , but indivisibility rounds any real machine load up to the next integer; that's why $⌈ 16/3 ⌉ = 6$ is the honest floor on OPT.
Confirm OPT $= 6$ . An explicit schedule reaching 6: ${5}$ , ${4, 2} = 6$ , ${3, 2} = 5$ → makespan $6$ . So the lower bound $6$ is achieved, $OPT = 6$ . Why this step? A matching upper (a real schedule) plus the lower bound pins OPT exactly.
Compare. $ALG = 6 = OPT$ — greedy is optimal on this instance. Why this step? Forming $ALG / OPT$ tells us the true performance, not just the guarantee.

Verify (units!): loads are in CPU-seconds; makespan $6$ CPU-seconds $\leq 2 \cdot OPT = 12$ CPU-seconds ✓. Performance ratio $= 6/6 = 1$ . The guarantee promised $\leq 12$ s; reality delivered $6$ s — the guarantee is a worst-case ceiling, not a prophecy (Greedy Algorithms).

C8 — The exam twist: maximization convention

Worked example Ex 9 — Max-Coverage, ratio flips direction (cell C8)

Statement. A maximization problem: you may pick $2$ sets to cover as many elements as possible. Sets: $S_{1} = {1, 2, 3}$ , $S_{2} = {3, 4}$ , $S_{3} = {4, 5}$ , over universe ${1, 2, 3, 4, 5}$ . A greedy algorithm picks the set covering the most new elements each round. It returns coverage $ALG$ ; OPT is the best possible with 2 sets. The famous greedy guarantee for Max-Coverage is $ρ = 1 - \frac{1}{e} \approx 0.632$ , meaning $ALG \geq ρ \cdot OPT$ .

Forecast: For maximization the inequality points the other way — do we write $ALG / OPT \leq ρ$ or $\geq ρ$ ?

Run greedy. Round 1: $S_{1}$ covers $3$ new elements ${1, 2, 3}$ — the most. Pick $S_{1}$ . Round 2: $S_{2}$ adds ${4}$ (1 new), $S_{3}$ adds ${4, 5}$ (2 new) — pick $S_{3}$ . Covered $= {1, 2, 3, 4, 5}$ , $ALG = 5$ . Why this step? Greedy maximizes marginal new coverage each round — that yields $ALG$ .
Find OPT. With 2 sets, can we cover all 5? $S_{1} \cup S_{3} = {1, 2, 3, 4, 5}$ → yes, $OPT = 5$ . Why this step? We need OPT to test the guarantee $ALG \geq ρ OPT$ .
Correct inequality. Maximization guarantee is $ALG \geq ρ \cdot OPT$ with $ρ \leq 1$ . Writing $ALG / OPT \leq ρ$ would be the min-problem form — that's the exam trap. Why this step? Direction of the ratio is set by whether more is better (max) or less is better (min).

Verify: $ALG = 5 \geq (1 - \frac{1}{e}) \cdot OPT = 0.632 \cdot 5 = 3.16$ ✓ (here we did far better — full coverage). The convention check: for max, bound $ALG$ from below; for min, bound from above.

Recall Active recall — cover the answers

What is the difference between the ALG/LB ratio and the ALG/OPT ratio? ::: ALG/LB is what we prove directly (bounded by rho); ALG/OPT is the true performance, obtained for free since LB <= OPT. Which triangle-inequality step lets Metric-TSP shortcutting not increase cost? ::: Replacing $a \to b \to c$ by direct $a \to c$ , since $d (a, c) \leq d (a, b) + d (b, c)$ . On a graph of $k$ disjoint edges, what performance ratio does matching-based Vertex Cover achieve? ::: Exactly $2$ ( $ALG = 2 k$ , $OPT = k$ ) — the tight worst case. On an odd cycle $C_{5}$ , what ratio does the algorithm get and why is it below 2? ::: $4/3$ , because $OPT = 3 > ∣ M ∣ = 2$ , so $2∣ M ∣/ OPT < 2$ . Why does the fraction form of the guarantee fail on an edgeless graph? ::: OPT $= 0$ gives $0/0$ ; use the inequality form $ALG \leq ρ \cdot OPT$ instead. What breaks when you run double-tree on non-metric TSP? ::: Shortcutting relies on the triangle inequality; without it the tour can cost far more than $2 \cdot LB$ . For a maximization problem, which direction does the ratio inequality point? ::: $ALG \geq ρ \cdot OPT$ with $ρ \leq 1$ (bound ALG from below).

Connections

Hinglish parent · NP-completeness
Vertex Cover · Maximum Matching — tight/loose cells C2, C3.
Minimum Spanning Tree · Triangle Inequality — metric & non-metric cells C4, C5.
Greedy Algorithms — load-balancing cells C6, C7.
PTAS and FPTAS · Inapproximability / PCP theorem — why non-metric TSP has no constant factor.