Foundations — Approximation algorithms — approximation ratio, examples

This page assumes you have seen none of the notation in the parent note. We build every symbol, one at a time, each resting on the one before it. Read top to bottom.

---

1. What is a "graph"? ($G$, $V$, $E$)

Before we can talk about Vertex Cover or MST, we need the object they live on.

The picture is everything here — a graph is a picture.

The little symbol $|V|$ means "how many dots" and $|E|$ means "how many lines". The two vertical bars $|\cdot |$ always mean size / count of a set. We use it constantly: $|M|$, $|C|$ below.

---

2. Sets and the "subset" symbol ($\subseteq$, $\in$, $\varnothing$)

A set is a bag of things with no duplicates and no order. We need three tiny symbols.

The arrow $\leftarrow$ (or $\leftarrow$) means "gets assigned": $C\leftarrow \varnothing$ reads "let $C$ start as empty."

---

3. Optimisation: minimise, maximise, and $\text{OPT}$

Every problem here asks for a best number.

---

4. Our algorithm's answer: $\text{ALG}$

So on the number line for a minimisation problem: $\text{OPT}$ sits at or below $\text{ALG}$. The question "how much worse is $\text{ALG}$?" is exactly the approximation ratio.

---

5. Ratios, inequalities, and $\rho$

Now the two symbols that carry the whole definition.

For maximisation the ratio is flipped: $\frac{\text{ALG}}{\text{OPT}}\ge \rho$ with $\rho \le 1$, because now $\text{ALG}\le \text{OPT}$ and we promise "at least $\rho$ times as good."

---

6. The trapping trick: lower bound $\text{LB}$

This is the deepest idea and it needs its own symbol.

Why is a floor useful? Because if we can also show our answer sits at most $\rho$ floors up, we sandwich OPT for free.

---

7. Special sub-objects: matching $M$, tree $T$

Two named lower bounds appear so often they get their own letters.

---

8. Polynomial time — the "fast" we insist on

---

Prerequisite map

---

Equipment checklist

Cover the right-hand side and test yourself before returning to the parent note.

• What does $G=(V,E)$ mean? ::: A graph: $V$ is the set of dots (vertices), $E$ the set of lines (edges) joining them.
• What does $|S|$ (vertical bars) mean? ::: The size / count of the set $S$.
• What does $C\subseteq V$ mean? ::: $C$ is a subset of $V$ — every element of $C$ is also a vertex in $V$.
• What is $\varnothing$ and what does $\leftarrow$ do? ::: $\varnothing$ is the empty set; $\leftarrow$ means "gets assigned", e.g. start $C$ as empty.
• What is $\text{OPT}$, and can we usually compute it? ::: The value of the best possible answer; usually no, not in polynomial time — but we can reason about it.
• What is $\text{ALG}$? ::: The value our fast algorithm actually outputs; a real computable number.
• For minimisation, why is $\rho \ge 1$? ::: Because $\text{ALG}\ge \text{OPT}$ already, so the ratio $\text{ALG}/\text{OPT}$ can never dip below 1.
• What does $\text{ALG}\le \rho \cdot \text{OPT}$ promise? ::: Our answer is never worse than $\rho$ times the best possible.
• What is a lower bound $\text{LB}$? ::: A quickly-computable number proven to satisfy $\text{LB}\le \text{OPT}$ — a floor under the optimum.
• State the LB-LADDER. ::: $\text{ALG}\le \rho \cdot \text{LB}\le \rho \cdot \text{OPT}$; prove the left step directly, get the right step free from $\text{LB}\le \text{OPT}$.
• What is a matching $M$? ::: A set of edges no two of which share a vertex.
• What is a spanning tree $T$? ::: A loop-free set of edges connecting all vertices; $\text{cost}(T)$ is the sum of its edge lengths.
• Why do we demand polynomial time? ::: It is our line for "practically fast"; exponential $2^n$ blows up as input grows.

---

Connections

• Approximation algorithms — approximation ratio, examples — the parent this page feeds.
• NP-completeness — why exact solutions are believed impossible fast.
• Vertex Cover · Maximum Matching — matching as a lower bound.
• Minimum Spanning Tree — tree cost as a lower bound.
• Greedy Algorithms · Triangle Inequality · PTAS and FPTAS · Inapproximability / PCP theorem.