Exercises — Approximation algorithms — approximation ratio, examples

WHAT we do: apply the definition $\text{ALG}/\text{OPT}\le \rho$ directly (this is rung 2 of the LB-LADDER read off in reverse). WHY: for minimization the ratio bounds $\text{ALG}$ from above. $\text{ALG}\le \rho \cdot \text{OPT}=2\times 30=60.$ So the answer is at most 60. Note it could be anything from $30$ (perfect) up to $60$ — the guarantee is only the ceiling.

No. For maximization the ratio bounds $\text{ALG}$ from below: $\text{ALG}\ge \rho \cdot \text{OPT}=\frac{1}{2}\text{OPT}.$ A max-algorithm that returned at most half of optimum would be useless — you want a guarantee that you get at least some fraction. The correct statement is $\text{ALG}/\text{OPT}\ge \frac{1}{2}$.

The size of the maximal matching $M$ we greedily built, i.e. $\text{LB}=|M|$. Every vertex cover needs $\ge 1$ vertex per disjoint matched edge, so $|M|\le \text{OPT}$ (rung 2); and our algorithm outputs $2|M|$ (rung 1).

WHAT we do: greedily pick uncovered edges, add both endpoints, delete touching edges.

• Pick edge $\{1,2\}$: add $1,2$ to $C$. Delete edges touching $1$ or $2$ → deletes $\{1,2\}$ and $\{2,3\}$.
• Remaining edge $\{3,4\}$: add $3,4$ to $C$. Delete it.
• $C=\{1,2,3,4\}$, so $\text{ALG}=4$.

OPT: the set $\{2,3\}$ covers all three edges ($\{1,2\}$ via $2$, $\{2,3\}$ via either, $\{3,4\}$ via $3$), so $\text{OPT}=2$. Ratio realised: $\text{ALG}/\text{OPT}=4/2=2$. This input is tight — it hits the worst case exactly.

WHAT we do: place jobs one by one on the least loaded machine.

Makespan $L=7$. WHY the 2-guarantee holds here (climbing the LB-LADDER): let $j$ be the last job placed on the busiest machine ($t_j=2$). Just before it was added that machine was the least loaded, so every machine had load $\ge L-t_j=5$; summing over all $m$ machines gives $\sum t_k\ge m(L-t_j)$, i.e. $L-t_j\le \frac{1}{m}\sum t_k$. Now use the two lower bounds (rung 1 uses both, rung 2 says each is $\le \text{OPT}$): $L=(L-t_j)+t_j\le \underset{\le \text{OPT}}{\underbrace{\frac{1}{m}\sum t_k}}+\underset{\le {\max }_k{t}_k\le \text{OPT}}{\underbrace{t_j}}\le 2\text{OPT}.$ Numbers: average $=\frac{12}{2}=6$; $\max t_k=3$. So $\text{OPT}\ge 6$; true $\text{OPT}=6$ ($[3,3]$ on one machine, $[2,2,2]$ on the other). Realised ratio $=7/6\approx 1.167$ — well under the guaranteed 2, exactly as the ladder promises.

WHY the 2-guarantee holds here (climbing the LB-LADDER): the lower bound is $\text{LB}=\text{cost}(T)$, the MST cost. Rung 1: the Euler walk of the doubled tree costs $2\text{cost}(T)$, and shortcutting repeated cities (triangle inequality) never increases cost, so $\text{ALG}\le 2\text{cost}(T)=2\text{LB}$. Rung 2: deleting one edge of any optimal tour leaves a spanning tree (see L3.2), and the MST is the cheapest tree, so $\text{cost}(T)\le \text{OPT}$. Chaining: $\text{ALG}\le 2\text{cost}(T)\le 2\text{OPT}.$ Numbers: $2\text{cost}(T)=80$, so $\text{ALG}\le 80$; and $\text{cost}(T)\le \text{OPT}$ gives $\text{OPT}\ge 40$. Combining: $40\le \text{OPT}\le \text{ALG}\le 80$.

WHY this graph: a perfect matching of size $n$ exists (pair left $i$ with right $i$), and the algorithm grabs both endpoints of each. The figure below shows the $n=3$ case — read it alongside this solution.

• ALG (blue-filled vertices in the figure): the algorithm can build a maximal matching of $n$ disjoint edges (the orange edges $L_i$–$R_i$). Each contributes 2 vertices → $C=\{L_1,\dots ,L_n,R_1,\dots ,R_n\}$, $\text{ALG}=2n=6$.
• OPT (green rings in the figure): take just one side, say all $n$ left vertices. Every edge has a left endpoint, so it is covered. Hence $\text{OPT}\le n$. And $\text{OPT}\ge n$ because a maximal matching of size $n$ forces $\ge n$ vertices. So $\text{OPT}=n=3$.
• Ratio: $\text{ALG}/\text{OPT}=2n/n=2$.

This is a family of inputs (one per $n$) that forces the ratio to exactly 2, so no analysis of this algorithm can prove a constant below 2.

WHAT a tour is: a cycle visiting all $n$ vertices, using $n$ edges. Delete one edge: we now have $n-1$ edges on $n$ vertices, still touching every vertex (each vertex had degree 2 in the cycle; the two endpoints of the removed edge drop to degree 1, the rest stay 2 — nobody is isolated). Why it's a tree: the remaining graph is a single path — connected (a cycle minus one edge stays connected) and acyclic (removing the one edge of the only cycle kills all cycles). A connected acyclic graph spanning all vertices is a spanning tree. Cost inequality: this spanning tree costs $\le \text{OPT}$ (it's part of the tour). The minimum spanning tree is $\le$ any spanning tree, so $\text{cost(MST)}\le \text{cost(tour minus one edge)}\le \text{OPT}.✓$

Only average, huge job fails: $m=2$, jobs $[10,1,1]$. Average $=12/2=6$, but a single job of size $10$ must go somewhere, so $\text{OPT}\ge 10>6$. The average bound is too weak; we need $\max t_k=10$. Only max, tiny jobs fails: $m=2$, jobs $[1,1,1,1]$. $\max t_k=1$, but four unit jobs on two machines force $\text{OPT}\ge \frac{4}{2}=2>1$. Here the average bound $=2$ is the tight one.

Conclusion: the greedy proof uses $L\le (L-t_j)+t_j\le \text{avg}+\max \le 2\text{OPT}$, and both pieces can individually be the binding constraint — neither alone suffices.

WHAT LPT does: sort $[5,4,4,3,2,2]$ (already sorted), place biggest first.

Makespan $L=7$. WHY it beats $2\text{OPT}$ (LB-LADDER): the same two lower bounds apply. The average is $\frac{1}{m}\sum t_k=\frac{20}{3}\approx 6.67$, so $\text{OPT}\ge \frac{20}{3}$. Now the integer trick: every job size is an integer, so every machine load — a sum of integers — is an integer, hence $\text{OPT}$ is an integer; by the "round a lower bound UP" corner-case box above we may strengthen $\text{OPT}\ge \frac{20}{3}$ to $\text{OPT}\ge \lceil \frac{20}{3}\rceil =7$. Also $\max t_k=5\le \text{OPT}$. The general greedy proof already guarantees $L\le \text{avg}+\max t_k=\frac{20}{3}+5\approx 11.67\le 2\text{OPT}$. But LPT does far better: since $\text{OPT}\ge 7$ and we achieved $L=7$, here $\text{OPT}=7$ (realised by $(5,2),(4,3),(4,2)=(7,7,6)$) and the ratio is exactly $1$ — comfortably inside the $2\text{OPT}$ ceiling.

WHAT we do: run two guaranteed algorithms and keep the minimum-cost output; the guarantee for the kept tour is the smaller of the two ceilings. WHY (LB-LADDER, applied to each algorithm then combined): each algorithm has already climbed its own ladder against the MST/tour lower bounds, giving us two upper bounds on its output:

• Double-tree: ${\text{ALG}}_1\le 2\cdot \text{OPT}=2\times 100=200$.
• Christofides: ${\text{ALG}}_2\le \frac{3}{2}\cdot \text{OPT}=\frac{3}{2}\times 100=150$.

We keep $\text{ALG}=\min ({\text{ALG}}_1,{\text{ALG}}_2)$. Since $\text{ALG}\le {\text{ALG}}_2\le 150$, the kept tour is guaranteed: $\text{ALG}=\min ({\text{ALG}}_1,{\text{ALG}}_2)\le \min (200,150)=150.$ Ratio: dividing by $\text{OPT}=100$, $\text{ALG}/\text{OPT}\le 150/100=\frac{3}{2}$, so the combined procedure is a $\boxed{\frac{3}{2}\text{-approximation}}$. General principle: running an extra approximation alongside and keeping the best can only tighten the guarantee — the combined ratio is the minimum (best) of the individual ratios, never their product and never worse than either alone.

With one machine, every job runs on it, so makespan $={\sum }_k{t}_k$ for any ordering. Thus $\text{ALG}=\text{OPT}=\sum t_k$ and the ratio is exactly $1$. Via the LB-LADDER: the average bound $\frac{1}{m}\sum t_k=\sum t_k$ already equals the answer, so $\text{LB}=\text{OPT}$ and the ladder collapses to equality. Degenerate case: no approximation needed when $m=1$.

Idea: flood with tiny jobs to balance the machines, then drop one big job. $m=2$, jobs $=[1,1,2]$ processed in this order.

• Job $1$ → M1: $(1,0)$.
• Job $1$ → M2: $(1,1)$.
• Job $2$ → M1 (tie, pick M1): $(3,1)$.

Greedy makespan $=3$. OPT: put the $2$ alone, the two $1$s together: loads $(2,2)$, $\text{OPT}=2$. Ratio $=3/2=2-\frac{1}{2}=2-\frac{1}{m}$. This matches the known tight bound for greedy list-scheduling on $m=2$.

Where it breaks: the shortcutting step replaces $a\to b\to c$ by $a\to c$ and claims $d(a,c)\le d(a,b)+d(b,c)$ — this is exactly the Triangle Inequality. Without it, $d(a,c)$ can be astronomically larger than the detour, so shortcutting may inflate cost without bound. The whole "$\le 2\text{cost}(T)$" line collapses. Deeper reason: general TSP admits no constant-factor approximation unless $\text{P}=\text{NP}$ (a reduction from Hamiltonian Cycle plants a giant edge weight that any constant-factor algorithm would be forced to avoid, thereby solving Hamiltonicity). See Inapproximability / PCP theorem. So no clever fix can exist — the barrier is complexity-theoretic, not a missing trick.

WHAT we combine: two lower bounds, added — this is the LB-LADDER with two rung-2 pieces. $\text{ALG}\le \underset{\le \text{OPT}}{\underbrace{\text{LB}}}+\underset{\le \text{OPT}}{\underbrace{\underset{k}{\max }{t}_k}}\le \text{OPT}+\text{OPT}=2\text{OPT}.$ Justification, term by term:

• $\text{LB}=\frac{1}{m}\sum t_k\le \text{OPT}$: some machine gets at least the average load, so the optimum makespan is $\ge$ the average.
• ${\max }_k{t}_k\le \text{OPT}$: the biggest single job must run on some machine, so the optimum makespan is $\ge$ that job's size.
• Rung 1 is the hypothesis $\text{ALG}\le \text{LB}+{\max }_k{t}_k$ (proved directly about the algorithm); rung 2 replaces each of the two summands by $\text{OPT}$.

Resulting ratio: $\boxed{\rho =2}$, i.e. the algorithm is a 2-approximation. This is exactly the greedy load-balancing analysis of L2.2, generalised: whenever your algorithm's cost decomposes into a bounded number $k$ of pieces each $\le \text{OPT}$, you get a $k$-approximation for free.

• L1: guarantee = deterministic cost ceiling, not a probability.
• L2: report the actual output, distinguish it from the bound; every guarantee is a climb of the LB-LADDER.
• L3: pick the right lower bound; sometimes you need two.
• L4: best-of-several takes the minimum guarantee; with integer objectives you may round a real lower bound up (L4.1).
• L5: tight examples validate the analysis; complexity barriers block impossible fixes.
• Corner case: ratios need non-negative objective values; $\text{OPT}=0$ forces $\text{ALG}=0$, negative weights fall outside the framework.