LP rounding
An LP relaxation hands you a fractional answer — variables sitting at values like 0.3 or 0.5 or 0.8 — but the real problem needs honest yes/no decisions. LP rounding is the step that converts those fractions back into a valid 0/1 solution, while controlling how much you pay for the conversion. The art is to round in a way that (a) keeps every constraint satisfied and (b) does not inflate the cost by more than a provable factor over the LP optimum.
The cleanest example is, once more, vertex cover, and it gives back the factor 2. Solve the relaxation; you get fractional values x_i in [0, 1]. Now round by a simple threshold: put vertex i into the cover exactly when x_i >= 1/2. First, is the result a valid cover? For any edge (i, j) the LP guaranteed x_i + x_j >= 1, so at least one of the two must be >= 1/2 (they cannot both be below 1/2 or their sum would be under 1) — hence at least one endpoint is rounded up, and the edge is covered. Second, what is the cost? Every variable you rounded up to 1 was already at least 1/2, so rounding at most doubles it: the rounded cost is at most 2 * (sum of x_i) = 2 * LP-OPT. And since LP-OPT <= integer-OPT, the rounded cover is at most 2 * OPT. That is a complete, self-contained 2-approximation derived purely from the LP — no matching needed.
Why this method earns its place: it is general and principled. You do not need a clever problem-specific trick like maximal matching; you write the 0/1 program, relax it, solve the LP with a generic solver, and round by a rule you can analyze. The same template gives approximations for many covering and packing problems. The honest limits: not every problem has a threshold that both preserves feasibility and gives a good factor, so the rounding rule must be designed per problem; the quality you can achieve is fundamentally capped by the integrality gap (if the LP optimum is far below the integer optimum, no rounding can close that distance); and deterministic thresholds sometimes lose to randomized rounding, which can do better on average.
Solve the vertex-cover LP and get x = (0.7, 0.3, 0.6, 0.5) for vertices A,B,C,D. Round at threshold 1/2: A (0.7>=0.5) in, B (0.3<0.5) out, C (0.6>=0.5) in, D (0.5>=0.5) in. Every edge had endpoint-sum >= 1, so each edge keeps a rounded-up endpoint — a valid cover, costing at most twice the LP value.
Round x_i up iff x_i >= 1/2: feasibility from the edge constraints, cost at most 2 * LP-OPT.
The achievable factor is bounded by the integrality gap: if the LP optimum sits well below the integer optimum, no rounding of that LP can do better than the gap. Rounding cannot beat the relaxation it starts from; choose a tight formulation.