An approximation algorithm for minimum vertex cover returns a solution of size 24. Given a 2-approximation guarantee, what can you conclude about the size of the optimal solution?
AThe optimal solution has size at most 12
BThe optimal solution has size exactly 12
CThe optimal solution has size at least 12
DThe optimal solution has size at most 24
A 2-approximation guarantees ALG ≤ 2 · OPT, so OPT ≥ ALG / 2 = 12. You can only say the optimal is *at least* 12 — not exactly 12, and not at most 12. The approximation ratio bounds how far above optimal the algorithm can go, which gives a lower bound on OPT from the algorithm's output, not an upper bound.
Question 2 Multiple Choice
What is the key difference between a PTAS and an FPTAS for an optimization problem?
AA PTAS gives a constant-factor approximation; an FPTAS gives a (1+ε)-approximation
BIn a PTAS, running time is polynomial in n for each fixed ε but may grow exponentially as ε→0; in an FPTAS, running time is also polynomial in 1/ε
CA PTAS requires the problem to be in APX; an FPTAS works on any NP-hard problem
DA PTAS approximates within 1% of optimal; an FPTAS approximates within 0.1% of optimal
Both PTAS and FPTAS give (1+ε)-approximations, but at different computational costs. A PTAS runs in polynomial time for any fixed ε, but the exponent may depend on ε (e.g., n^{1/ε}), making it impractical for very small ε. An FPTAS requires time polynomial in both n and 1/ε simultaneously (e.g., O(n²/ε)), so high precision is achievable without exponential blowup. The knapsack problem has an FPTAS; Euclidean TSP has a PTAS but not an FPTAS.
Question 3 True / False
An approximation ratio of 2 is a worst-case guarantee, so the algorithm's actual output may be much closer to optimal on typical inputs.
TTrue
FFalse
Answer: True
Approximation ratios are worst-case bounds — they guarantee the algorithm never exceeds a certain multiple of OPT, but say nothing about average-case performance. In practice, algorithms with a 2-approximation guarantee often return solutions within 10–20% of optimal on real instances. The ratio defines the theoretical worst case, not the expected output quality.
Question 4 True / False
Since most NP-hard problems are computationally equivalent under polynomial reductions, they are most equally difficult to approximate.
TTrue
FFalse
Answer: False
NP-hardness means all NP-hard problems are equivalent in terms of exact solvability, but their approximability varies enormously. Vertex cover has a 2-approximation; knapsack has an FPTAS (arbitrarily good polynomial approximation); graph coloring cannot be approximated within n^{1−ε} for any ε > 0 unless P = NP. The PCP theorem and gap-preserving reductions reveal a rich approximability hierarchy that does not follow from NP-hardness alone.
Question 5 Short Answer
Explain why the greedy maximal-matching algorithm for vertex cover achieves a 2-approximation. What property of the optimal solution provides the key lower bound?
Think about your answer, then reveal below.
Model answer: The algorithm finds a maximal matching (a set of edges with no shared endpoints, where no more edges can be added) and returns both endpoints of every matched edge. The key: the optimal vertex cover must include at least one endpoint of each matched edge — otherwise that edge would be uncovered. So OPT ≥ |matching|. The algorithm takes 2·|matching| vertices, giving a ratio of at most 2·|matching| / OPT ≤ 2·|matching| / |matching| = 2.
The analysis works by finding a structural lower bound on OPT (every cover must hit every matched edge) and then bounding the algorithm's output against that lower bound. The algorithm never computes OPT directly. This 'bound the algorithm against a lower bound on OPT' strategy — using problem structure rather than knowing the optimum — is the backbone of most approximation analyses.