Questions: Approximation Algorithms (LP Relaxation and Primal-Dual)

Question 1

The LP relaxation of the minimum vertex cover problem has an integrality gap of exactly 2. What does this mean, and why does it immediately yield a 2-approximation algorithm?

• A. The LP relaxation always returns a solution with cost exactly twice the integer optimum
• B. The ratio between the optimal integer solution and the optimal fractional solution is at most 2 for all instances, and rounding all fractional variables >= 1/2 to 1 (and others to 0) produces a valid vertex cover with cost at most 2 times the LP optimum, which is at most 2 times the integer optimum
• C. The LP relaxation runs in time O(n^2) instead of O(n)
• D. Every vertex cover can be converted to a fractional solution by dividing all values by 2

Answer: (B)

For any edge (u,v), the LP constraint x_u + x_v >= 1 means at least one of x_u, x_v is >= 1/2. Rounding all variables >= 1/2 to 1 covers every edge (at least one endpoint rounds to 1). The cost of the rounded solution is at most 2 * LP_OPT because each variable at most doubles. Since LP_OPT <= OPT_integer (relaxation only makes the feasible region larger), the rounded solution costs at most 2 * OPT. The integrality gap is exactly 2 because some instances (e.g., odd cycles) have LP_OPT = n/2 but OPT = ceil(n/2), with ratio approaching 2.

Question 2

In the primal-dual method for approximation algorithms, the dual solution provides a LOWER BOUND on the optimal value, while the primal solution provides the actual (feasible) solution with an UPPER BOUND.

• T. True
• F. False

Answer: True

This is the heart of the primal-dual approach. For a minimization problem, weak duality says: any feasible dual solution value <= optimal primal value. So the dual gives a lower bound on OPT. The algorithm constructs a feasible primal (integer) solution and a feasible dual solution such that primal_cost <= alpha * dual_value for some factor alpha. Then primal_cost <= alpha * dual_value <= alpha * OPT, proving an alpha-approximation. The algorithm never needs to solve the LP — it just needs to produce feasible primal and dual solutions with a bounded ratio.

Question 3

Explain why randomized rounding of an LP relaxation for set cover achieves O(log n)-approximation, and why this is essentially optimal.

Model answer: Solve the LP relaxation, which assigns fractional values x_S to each set S. Include each set independently with probability x_S. An element covered by sets of total fractional value v is uncovered with probability at most product(1 - x_S) <= e^(-v) <= e^(-1) (since LP feasibility requires sum >= 1 for each element). Repeating O(log n) times (or scaling probabilities by c*log n) ensures every element is covered with high probability, at expected cost O(log n) * LP_OPT. Since LP_OPT <= OPT, this gives O(log n)-approximation. This is essentially optimal: the hardness result of Dinur and Steurer (2014) shows set cover cannot be approximated better than (1-epsilon) * ln n unless P = NP. The LP relaxation's integrality gap is also Theta(log n), so LP-based methods cannot do better.

The argument uses the inequality 1-x <= e^(-x) and the fact that LP feasibility constrains the total fractional coverage of each element to be at least 1. Randomized rounding converts fractional coverage into probabilistic coverage, and log n repetitions handle the union bound over n elements.

Question 4

The primal-dual method requires explicitly solving a linear program before constructing the approximation.

• T. True
• F. False

Answer: False

A major advantage of the primal-dual method is that it does NOT require solving the LP. Instead, it directly constructs feasible primal and dual solutions through a combinatorial algorithm — typically growing the dual solution until some constraint becomes tight, then adding the corresponding primal element. The LP and its dual are used only in the ANALYSIS to prove the approximation ratio. This makes primal-dual algorithms combinatorial, often simpler, and sometimes faster than LP-based rounding approaches. Classic examples include the primal-dual 2-approximation for the feedback vertex set problem and Jain's iterative rounding for Steiner network.