A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Approximation algorithms provide provably near-optimal solutions to NP-hard optimization problems in polynomial time. LP relaxation replaces integer constraints with continuous ones, solves the resulting linear program, and then rounds the fractional solution to an integer solution — the integrality gap bounds the worst-case approximation ratio. The primal-dual method constructs feasible primal and dual solutions simultaneously, using complementary slackness conditions to guide the algorithm and weak duality to prove the approximation guarantee. For vertex cover, LP relaxation yields a 2-approximation (round all variables >= 1/2); for set cover, randomized rounding of the LP relaxation gives an O(log n)-approximation matching the hardness of approximation lower bound. These techniques transform optimization problems into algebraic ones where duality theory provides the performance guarantee.
NP-hardness tells you that finding optimal solutions is (almost certainly) intractable. Approximation algorithms respond by asking: how close to optimal can we get in polynomial time? The answer depends on the problem, and the most powerful tools for both designing approximation algorithms and proving their guarantees come from linear programming duality.
LP relaxation is the most natural approach. Formulate the optimization problem as an integer linear program (ILP), drop the integrality constraints to get a linear program (LP), solve it, and round the fractional solution to an integer one. The LP optimum is a lower bound on the ILP optimum (for minimization), so if rounding increases the cost by at most a factor alpha, you have an alpha-approximation. For vertex cover, the rounding is simple: every vertex with LP value >= 1/2 enters the cover. Every edge is covered (its LP constraint forces at least one endpoint to >= 1/2), and the cost at most doubles. The factor of 2 is tight for this rounding scheme because the LP's integrality gap is exactly 2.
The primal-dual method is more sophisticated and often yields combinatorial algorithms. Instead of solving the LP, you simultaneously construct a feasible primal solution (the approximate answer) and a feasible dual solution (the lower bound certificate). The algorithm typically grows dual variables until some dual constraint becomes tight, then adds the corresponding primal element. Weak duality guarantees that the dual objective is a lower bound on the optimum, so if the primal cost is at most alpha times the dual objective, you have an alpha-approximation. The beauty is that the LP is never solved — it appears only in the proof. This yields fast, combinatorial algorithms with provable guarantees.
The deepest results in approximation algorithms connect the integrality gap of an LP (or SDP) relaxation to the hardness of approximation. The Unique Games Conjecture, if true, implies that for many problems the integrality gap of the natural SDP relaxation exactly characterizes the best achievable approximation ratio. For set cover, the Theta(log n) approximation ratio matches both the LP integrality gap and the hardness lower bound — the LP relaxation captures the problem's approximability perfectly. Understanding these connections between relaxation strength, rounding techniques, and computational hardness is the central project of modern approximation algorithm theory.