Approximating NP-Complete Problems with Relaxed Linear Programs
Motivation
Many NP-complete problems — vertex cover, set cover, facility location, max-cut — admit a clean formulation as integer linear programs but become tractable the moment the integrality constraint is dropped, turning into ordinary linear programs solvable in polynomial time.
This suggests a recipe for approximation:
- Write the problem as an ILP.
- Solve the LP relaxation.
- Round the fractional solution to an integer one, and bound the loss.
The strategy works remarkably often. For some problems (vertex cover) the rounded solution is provably within a small constant factor of the optimum. For others (set cover) randomized rounding gives an \(O(\log n)\) approximation. The framework — relax, solve, round, bound — has powered approximation algorithms for half a century (Kleinberg and Tardos 2005).
The general template
Given an ILP \[ \min c^\top x \quad \text{s.t.} \quad A x \ge b, \quad x \in \{0, 1\}^n, \] its LP relaxation is \[ \min c^\top x \quad \text{s.t.} \quad A x \ge b, \quad x \in [0, 1]^n. \]
The relaxation has a strictly larger feasible set, so for a minimization problem \[ \text{LP-OPT} \le \text{ILP-OPT}. \]
Round the LP optimum \(x^*\) to an integer \(\hat x\) that remains feasible. The integrality gap \[ \text{gap} = \max_{\text{instances}} \frac{\text{ILP-OPT}}{\text{LP-OPT}} \] bounds the achievable approximation ratio: any rounding scheme produces a solution at most \(\text{gap}\) times the LP, so at most \(\text{gap}\) times the ILP.
Worked example: vertex cover
Problem. Given graph \(G = (V, E)\), find a smallest \(S \subseteq V\) that touches every edge.
ILP. \[ \min \sum_{v} x_v \quad \text{s.t.} \quad x_u + x_v \ge 1 \; \forall (u, v) \in E, \quad x_v \in \{0, 1\}. \]
LP relaxation. Same constraints, \(x_v \in [0, 1]\).
Rounding. Round each \(x_v^* \ge 1/2\) up to \(1\), the rest down to \(0\). Set \[ S = \{ v : x_v^* \ge 1/2 \}. \]
Feasibility. For any edge \((u, v)\), \(x_u^* + x_v^* \ge 1\), so at least one of them is \(\ge 1/2\) and ends up in \(S\).
Approximation ratio. \(|S| = \sum_{v : x_v^* \ge 1/2} 1 \le \sum_v 2 x_v^* = 2 \cdot \text{LP-OPT} \le 2 \cdot \text{ILP-OPT}\). So this is a 2-approximation.
This is the famous “fractional half” rounding scheme, and 2-approximation is essentially the best known polynomial-time bound for vertex cover (up to lower-order terms — improving to \(2 - \epsilon\) would refute the Unique Games Conjecture).
Worked example: set cover
Problem. Given universe \(U\) of \(n\) elements and sets \(S_1, \dots, S_m\) with costs \(c_j\), find a minimum-cost subcollection covering \(U\).
ILP. \[ \min \sum_j c_j x_j \quad \text{s.t.} \quad \sum_{j : u \in S_j} x_j \ge 1 \; \forall u \in U, \quad x_j \in \{0, 1\}. \]
LP relaxation. Same constraints, \(x_j \in [0, 1]\).
Rounding by randomization. Independently include each set \(S_j\) with probability \(\min(1, x_j^*)\). Repeat \(O(\log n)\) rounds until every element is covered.
Approximation ratio. Each repetition covers each element with probability \(\ge 1 - 1/e\), so \(O(\log n)\) rounds cover all elements with high probability, with expected total cost \(O(\log n) \cdot \text{LP-OPT}\). So this is an \(O(\log n)\)-approximation.
Hardness results (Feige’s \(\log n\)-inapproximability) show this is tight up to constants.
Why rounding works (and when it doesn’t)
The success of LP rounding depends on the integrality gap. For some problems the gap is bounded (vertex cover: \(2\), set cover: \(\Theta(\log n)\)); for others it can be unbounded (independent set: \(\Theta(n)\)). Problems with a small gap admit good LP-based approximations; problems with a large gap need different techniques.
When the LP solution is itself integer (no rounding needed), the algorithm is exact in polynomial time. This happens when the constraint matrix \(A\) is totally unimodular — bipartite matching, network flow, shortest paths, and assignment all enjoy this property.
Other rounding techniques
- Threshold rounding: round above some threshold up, below down (vertex cover).
- Randomized rounding: round each variable independently with probability equal to its fractional value (set cover, MAX-SAT).
- Pipage / dependent rounding: introduce correlations to preserve marginals while improving global structure (matroid problems, MAX-3-SAT).
- Iterative rounding: solve the LP, fix some variables to integer values, re-solve. Used in network design (Steiner tree, survivable network design).
When LP relaxation is the wrong tool
For problems with large integrality gap, LP relaxation gives weak bounds. Alternatives include:
- SDP relaxation: solves a semidefinite program; the gap is often smaller. Goemans-Williamson MAX-CUT (0.878-approximation) is the textbook example.
- Multiplicative weights: a fast, near-linear-time technique that often matches LP-based bounds, especially for packing/covering LPs.
- Combinatorial algorithms: greedy, local search, specialized DPs for restricted instances.