Questions: Approximation Algorithms and Approximation Ratios

Question 1

A greedy algorithm for vertex cover always produces a solution with at most twice as many vertices as optimal, running in polynomial time. A student claims this algorithm 'partially solves an NP-complete problem.' What is the most accurate characterization?

• A. The student is correct — producing any suboptimal solution in polynomial time partially solves NP-completeness
• B. The student is wrong — approximation algorithms are not 'partial solutions' but complete algorithms with provable guarantees, and finding a 2-approximation in polynomial time is a well-defined and fully achieved goal
• C. The algorithm cannot be correct because NP-complete problems cannot be solved in polynomial time under any conditions
• D. The algorithm is only valid if vertex cover is proved to be in P

Answer: (B)

Approximation algorithms do not 'partially solve' anything — they completely solve a precisely stated problem: find a solution within factor α of optimal in polynomial time. The 2-approximation for vertex cover achieves exactly this guarantee. The misconception conflates 'not finding the exact optimum' with 'not solving the problem fully,' but the approximation ratio is the stated objective, and it is met.

Question 2

For the Traveling Salesman Problem restricted to instances satisfying the triangle inequality, what is the best known polynomial-time approximation ratio?

• A. 2-approximation via minimum spanning tree doubling
• B. 1.5-approximation via Christofides' algorithm (MST plus minimum-weight perfect matching)
• C. No constant-factor approximation exists unless P = NP
• D. A PTAS exists, achieving (1 + ε) for any ε > 0

Answer: (B)

Christofides' algorithm achieves a 1.5 ratio for metric TSP: build an MST, find a minimum-weight perfect matching on odd-degree vertices, combine to form an Eulerian circuit, then shortcut repeated vertices. The triangle inequality ensures shortcuts don't increase total distance. Contrast this with general TSP (without triangle inequality), which has no constant-factor approximation unless P = NP — illustrating that the structure of an NP-hard problem, not just its hardness, determines approximability.

Question 3

A polynomial-time approximation scheme (PTAS) for a minimization problem guarantees a solution within (1 + ε) of optimal for any ε > 0, but the running time may grow as ε shrinks.

• T. True
• F. False

Answer: True

A PTAS gives you arbitrarily close approximations in polynomial time for each fixed ε, but the polynomial's degree or coefficient may depend on 1/ε. For example, a running time of O(n^(1/ε)) is polynomial for any fixed ε but grows steeply. This is still far better than exact exponential algorithms for large inputs, and problems with PTAS are considered 'almost tractable' compared to those that are inapproximable.

Question 4

Since vertex cover is NP-hard, no polynomial-time algorithm can guarantee a solution better than a constant factor away from optimal.

• T. True
• F. False

Answer: False

Vertex cover has a simple 2-approximation via greedy edge selection: pick any uncovered edge, add both endpoints, remove covered edges, repeat. The result uses at most twice the optimal. This is a polynomial-time guarantee. The NP-hardness of vertex cover means finding the EXACT optimum in polynomial time is (almost certainly) impossible — but it says nothing about the quality of approximations achievable.

Question 5

Why is knowing that a problem is NP-hard insufficient to determine how well it can be approximated? Give examples illustrating the range of approximability among NP-hard problems.

Model answer: NP-hardness only rules out polynomial-time exact algorithms (assuming P ≠ NP). Approximability is a separate question. Vertex cover (NP-hard) has a 2-approximation; metric TSP has a 1.5-approximation (Christofides); the knapsack problem has a PTAS yielding solutions within (1+ε) of optimal for any ε. But general TSP and set cover admit no constant-factor approximation (or only O(log n)), and some problems are inapproximable to any factor. NP-hardness is a single threshold; approximability is a rich spectrum.

The field of approximation algorithms exists precisely because NP-hardness is not a monolithic barrier — it is a floor below which exact algorithms cannot go, but above which the landscape varies enormously. Practical algorithm design depends critically on where a specific problem falls: a guaranteed-50%-suboptimal solution in milliseconds is often more valuable than a theoretically exact answer requiring centuries of compute.