JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

LP Relaxation and Rounding

The greedy guides found approximations by clever hand-arguments. This one hands you a factory: write the hard problem as a 0/1 program, relax the integrality to get a solvable linear program, then round the fractional answer back to a real solution — and prove what that costs.

Two new ideas, one old goal

So far in this rung you have earned approximations by hand: a clever maximal-matching trick gave the 2-approximation for vertex cover, a greedy logarithm gave the set cover guarantee, a spanning tree gave metric TSP. Each was a one-off insight. This guide replaces inspiration with a method that applies to a huge family of problems at once. The plan has exactly two moves: relax, then round.

The starting observation is that almost every combinatorial problem can be written as an integer program (IP): decide a 0/1 value for each object — include this vertex or not, pick this set or not — minimize a linear cost, subject to linear constraints. Vertex cover is the cleanest example. Give each vertex v a variable x_v that must be 0 or 1. The objective is to minimize the sum over all vertices of x_v (the cover's size). The constraint is that for every edge (u,v) at least one endpoint is chosen: x_u + x_v >= 1. That IP is an exact description of minimum vertex cover — but solving integer programs is NP-hard in general, so we have only moved the difficulty, not removed it.

minimize  sum over v of x_v        (cover size)
subject to  x_u + x_v >= 1   for each edge (u,v)
            x_v in {0,1}      <-- IP: NP-hard
            0 <= x_v <= 1     <-- LP relaxation: poly-time
The vertex-cover IP and its relaxation differ in one line: integers become a real interval.

Relaxing: from hard integers to an easy interval

The relaxation move is almost embarrassingly simple. Replace the demand `x_v in {0,1}` with the demand `0 <= x_v <= 1`. Now each variable may take any real value in that interval — a vertex can be 0.5 in the cover. This is the LP relaxation: a linear program, minimizing a linear objective over linear inequalities with continuous variables. The crucial fact is that, unlike its integer parent, a linear program is solvable in polynomial time (by the simplex method in practice, by interior-point or ellipsoid methods in provable polynomial time).

Here is the first load-bearing observation, and it holds for every minimization problem you relax this way. Every integer solution is also a fractional solution — the integers 0 and 1 live inside the interval [0,1]. So the LP is choosing from a strictly larger set of options than the IP. A minimizer that may search a larger feasible region can only do at least as well. Therefore OPT_LP <= OPT_IP = OPT: the LP optimum is a lower bound on the true optimum. That single inequality is the whole reason the method works — it gives us something concrete to measure our rounded solution against.

Rounding, exhibit one: vertex cover by threshold

Solve the LP and you get an optimal fractional vector x* with each x*_v somewhere in [0,1]. We need a real cover, so we must decide for each vertex: in or out. The threshold rounding rule is brutally simple — round x*_v up to 1 if x*_v >= 1/2, and down to 0 otherwise. Two things must be checked, and they are exactly the two things any rounding proof needs: that the result is feasible (a legal cover), and that its cost is not too far above OPT_LP.

  1. Feasibility. Take any edge (u,v). The LP constraint forced x*_u + x*_v >= 1, so the two values cannot both be below 1/2 (two numbers under 1/2 sum to under 1). Hence at least one endpoint has value >= 1/2 and gets rounded up to 1. Every edge keeps a chosen endpoint, so the rounded set is a legal vertex cover.
  2. Cost. Each variable was rounded up by at most a factor of 2: if it survives, x*_v >= 1/2, so 1 <= 2 * x*_v. Summing over the cover, its size is at most 2 * (sum of x*_v) = 2 * OPT_LP.
  3. Chain to OPT. Since OPT_LP <= OPT, the rounded cover has size at most 2 * OPT_LP <= 2 * OPT. That is a factor-2 guarantee: a polynomial-time algorithm that never returns a cover larger than twice the optimum.

Pause on what just happened. We recovered the same approximation ratio of 2 that the maximal-matching argument gave in guide 2 — but by a completely mechanical recipe that never mentioned matchings. The clever combinatorial insight has been replaced by 'write the IP, relax, threshold-round.' That is the real payoff: not a better ratio here, but a systematic route that you can point at the next problem and the next, where no clever insight is lying around.

Rounding, exhibit two: randomized rounding for set cover

Threshold rounding worked because every constraint had only two variables, so one was guaranteed to be large. Most problems are not so kind. Set cover has constraints like 'element e is covered by some chosen set,' and an element might sit in dozens of sets, each with a tiny fractional value — no single one crosses 1/2. The cure is to flip coins. In randomized rounding we treat each fractional value x*_S as a probability: independently pick set S into our solution with probability x*_S. This is one of the most elegant ideas in the whole subject.

Two questions, again: cost and feasibility. The expected cost is easy and beautiful: by linearity of expectation, the expected total cost is the sum over sets of (cost of S) times (probability x*_S) — which is exactly the LP objective, OPT_LP. So on average one round of coin-flipping costs no more than the lower bound itself. Feasibility is the subtle part: a single round might, by bad luck, leave some element uncovered. For an element e in sets whose fractional values sum to at least 1, the chance it is missed by all of them is at most 1/e (the base of natural logs) — better than even odds of being covered, but not a guarantee.

The fix is to repeat. Run the random rounding about c * ln(n) times independently and take the union of all sets ever chosen, where n is the number of elements. The chance a fixed element is still missed after that many rounds falls to roughly (1/e)^(c ln n) = n^(-c), so a union bound over all n elements makes the probability of any element being missed vanish. The cost grows by the same ln(n) factor, giving an O(log n)-approximation — matching the greedy guarantee from guide 2, but now obtained from the LP. Honesty check: this is a randomized algorithm, so its guarantees are about expectation and high probability, not an ironclad promise on every single run; a particularly unlucky execution could be worse.

How good can the lower bound be? The integrality gap

Everything above hangs on one number we should look in the eye. The LP gives a lower bound OPT_LP, but how loose is it — how big can the true optimum be compared to the fractional one? That worst-case ratio, taken over all instances, is the integrality gap: the largest possible OPT_IP / OPT_LP. It is a hard ceiling on this technique. No rounding scheme that compares its output to OPT_LP can ever prove an approximation ratio better than the integrality gap, because on the worst instance even the optimal integer solution is that many times bigger than the bound you are measuring against.

A vivid case is a triangle: three vertices, three edges. Setting every x_v = 1/2 satisfies each edge constraint (1/2 + 1/2 = 1) for a fractional cost of 3/2. But any integer cover of a triangle needs 2 vertices. So OPT_IP / OPT_LP = 2 / 1.5 = 4/3 here, and one can push families of graphs toward an integrality gap of 2 for vertex cover. That is exactly why our threshold rounding stopped at factor 2 and could not do better through this LP — the bound itself is off by up to a factor of 2, so no rounding could squeeze past it. The integrality gap is not a failure of cleverness; it is a property of the relaxation.

A second engine, and the limits of the whole approach

Solving the LP exactly is sometimes overkill, and there is a cousin method that often skips it entirely. The primal-dual method works with the LP and its dual at the same time: it grows a feasible dual solution (which, by LP duality, is itself a lower bound on OPT) and uses the dual to decide, combinatorially, what to put in the primal integer solution. Done right it yields the same factor-2 vertex cover and the same O(log n) set cover — but as a fast, often purely combinatorial algorithm that never calls an LP solver. It is the same lower-bound-and-round idea wearing work clothes; the primal-dual method is the engine behind many of the fastest approximation algorithms in practice.

Now the boundary you must respect. Relax-and-round is powerful but it is not a master key that unlocks every door. The quality of what you can prove is bounded below by the integrality gap, and that gap is sometimes terrible: for general set cover the gap is Theta(log n), so the LP simply cannot certify anything better than a logarithmic factor — and remarkably, complexity theory says no polynomial algorithm can do essentially better unless P = NP. For some problems the natural LP has an unbounded gap and is useless without strengthening. The lesson echoes the whole rung: a relaxation is a tool with a known reach, and part of using it well is knowing, before you start rounding, how far the lower bound can possibly take you.