the primal-dual method
Solving a linear program exactly, then rounding, works — but invoking a full LP solver feels heavy for something like vertex cover. The primal-dual method gets the same kind of guarantee WITHOUT ever solving an LP: it builds the integer solution and a certificate of its quality at the same time, by exploiting the duality between a problem and its 'dual'. The result is usually a simple, fast, combinatorial algorithm whose approximation factor falls out of the duality bookkeeping.
Here is the idea in plain terms. Every linear program (the primal, e.g. minimize the cover) has a partner LP called its dual (e.g. a packing problem on the edges), and weak duality guarantees that ANY feasible dual solution gives a lower bound on the primal optimum. The primal-dual method runs both at once: it starts with the dual variables at zero and the primal solution empty, then repeatedly RAISES dual variables (growing the lower bound) until some dual constraint becomes tight, and whenever a constraint goes tight it adds the corresponding element to the primal solution. For vertex cover: keep a 'budget' y_e on each still-uncovered edge; raise these budgets until a vertex's incident budgets sum to its cost (it goes 'tight'), then add that vertex to the cover and remove its edges. You can show each chosen vertex's cost is paid for by edge budgets, each edge pays at most two vertices, so the cover costs at most twice the total dual — and the total dual is a lower bound on OPT. That gives the 2-approximation again, now with no LP solver, just a loop raising budgets.
Why the method is prized: it produces fast, often greedy-looking algorithms with proven ratios, and the dual solution it builds is its own correctness certificate — you finish holding both an answer and a proof of near-optimality. It is the engine behind classic results for set cover, Steiner trees, facility location, and shortest-path-style network design. The honest scope: designing the dual and the raising schedule requires real insight, and the ratio you get depends on the structure you exploit; primal-dual is a powerful framework, not an automatic recipe, and like all relaxation methods it is ultimately limited by the integrality gap of the underlying LP.
Vertex cover via primal-dual: give every edge a budget starting at 0. Raise all uncovered edges' budgets together. When the budgets around vertex v sum to v's cost, v goes tight — add v to the cover, drop its edges. The summed budgets lower-bound OPT, each edge funds at most two chosen vertices, so cover <= 2 * (total budget) <= 2 * OPT.
Raise dual budgets until constraints go tight; the dual itself certifies the lower bound on OPT.
Weak duality is the load-bearing fact: any feasible dual is a lower bound on the primal OPT, so you never need to solve the LP — you only raise dual variables. The dual solution you end with is a built-in certificate of near-optimality.