Question bank — Approximation algorithms — approximation ratio, examples

False — the "2" is a worst-case cost multiplier, not a probability; the algorithm is deterministic and may be within 2× on every input, often much closer.

True — smaller $\rho \ge 1$ means the returned cost is bound closer to $\text{OPT}$, so the guarantee is tighter.

False — for maximization we want $\text{ALG}\ge \rho \cdot \text{OPT}$ with $\rho \le 1$, so $\rho$ closer to 1 is stronger; $0.9$ beats $0.5$.

True — $\text{ALG}/\text{OPT}\le 1$ combined with $\text{ALG}\ge \text{OPT}$ (min) forces $\text{ALG}=\text{OPT}$ on every input.

True — an FPTAS is poly in both $n$ and $1/ϵ$, which is a stronger requirement than poly in $n$ alone, so it satisfies the PTAS definition too; hence $\text{FPTAS}\subseteq \text{PTAS}$.

False — you compare $\text{ALG}$ against a computable lower bound $\text{LB}\le \text{OPT}$ (matching size, MST cost); $\text{OPT}$ sits in the middle and is never computed.

False — picking only one endpoint of a matched edge can leave the other edges (touching the unpicked vertex) uncovered, so it need not produce a valid cover at all.

False — a smaller $\text{LB}$ only makes $2\text{LB}$ smaller, i.e. a tighter bound on $\text{ALG}$; the guarantee $\text{ALG}\le 2\text{OPT}$ still holds since $\text{LB}\le \text{OPT}$.

False — it needs the Triangle Inequality so that shortcutting cannot increase cost; on non-metric instances the guarantee collapses.

True — e.g. general (non-metric) TSP and Max-Clique; this is shown via inapproximability results.

Wrong — $|M|$ is a lower bound on $\text{OPT}$, not equal to it; the cover uses $2|M|$ vertices and $\text{OPT}$ can be anywhere between $|M|$ and $2|M|$.

Wrong — deleting an edge gives a spanning tree, whose cost is $\ge$ the minimum spanning tree; so $\text{cost(MST)}\le \text{that tree}\le \text{OPT}$, using MST as the cheapest tree.

Wrong — 2 is a valid (just weaker) guarantee; $3/2$ is a tighter guarantee. A larger valid $\rho$ is not "incorrect," only less impressive.

Wrong reasoning, right bound — OPT $\ge$ average because someone must carry at least the average; OPT could be strictly larger if one job is huge.

Wrong direction — a max-guarantee bounds from below: you need $\text{ALG}\ge 0.5\text{OPT}$. Bounding $\text{ALG}$ from above says nothing about how good it is.

Wrong — it is only a 2-approximation; greedy can build an uneven schedule that a smarter reassignment would beat, so it is not exact.

Because computing $\text{OPT}$ is the NP-hard problem itself; a lower bound like $|M|$ or MST cost is poly-time computable, and the "LB-LADDER" $\text{ALG}\le \rho \text{LB}\le \rho \text{OPT}$ lets $\text{OPT}$ stay unknown.

Because the Triangle Inequality says a direct edge $a\to c$ is no longer than the detour $a\to b\to c$, so skipping an already-visited $b$ can only shorten (or tie) the walk.

Because the single largest job must be placed somewhere, and that one machine alone already has load $\ge {\max }_k{t}_k$, so the makespan can't be smaller.

Because disjointness forces any cover to spend a distinct vertex on each matched edge, giving $\text{OPT}\ge |M|$; if edges shared vertices, one cover-vertex could handle several and the bound would fail.

A constant factor (say 2) is fixed, whereas a PTAS lets you demand any accuracy $1+ϵ$; the PTAS can get arbitrarily close to optimal, the constant-factor cannot.

Because we split the finishing load as $L=(L-t_j)+t_j$; the first piece is bounded by the average ($\le \text{OPT}$) and the second by the single-job max ($\le \text{OPT}$), so their sum is $\le 2\text{OPT}$.

The matching is empty, $\text{ALG}=0=\text{OPT}$; the ratio is defined as $1$ (or trivially satisfied), since there are no edges to cover.

Yes trivially: with one city the tour cost is $0$; with two cities the MST is the tour up to doubling, and every bound $\text{cost(MST)}\le \text{OPT}$ still holds degenerate-ly.

All jobs pile onto the one machine, so $\text{ALG}=\sum t_k=\text{OPT}$; the greedy is exact and the ratio is $1$.

Yes — that giant job forces $\text{OPT}\ge {\max }_k{t}_k$, and greedy places everything else around it; the makespan is at most $\text{OPT}+t_j\le 2\text{OPT}$ as proven.

Still fine — the triangle inequality holds with equality/zero terms, shortcutting cannot increase cost, and $\text{cost(MST)}\le \text{OPT}$ remains valid; ratios never require strictly positive weights.

Yes — the algorithm always returns $2|M|$ vertices regardless; on such an instance it is a worst case, achieving the full ratio $2$ rather than beating it.

Not necessarily — the ratio depends on $|M|$ versus $\text{OPT}$, and even a maximum matching can force $\text{ALG}=2|M|$ up to $2\text{OPT}$; maximality is enough, maximum-ness gives no extra guarantee here.