rounding an LP relaxation

A simple example of computing an approximate solution by rounding the solution to a linear-program relaxation.

The basic paradigm:

  1. Model your problem as an integer linear program.

  2. Solve its linear program relaxation.

  3. Somehow round the solution x^* of the relaxed problem to get a solution \tilde x of the original problem.

The rounding step is typically most easily done with a so-called randomized rounding scheme.

Rounding a relaxation is one of two standard ways to use linear-programming relaxations to design approximation algorithms. (The other way is the primal-dual method.)

Trivial example: vertex cover

For a trivial example of rounding, consider minimum-cost Vertex Cover. Given a graph G=(V,E) with vertex costs, the problem is to find a vertex cover (a subset of the vertices touching all edges) of minimum total cost. A standard integer program for the problem is

\[ \renewcommand{\mathspread }{\, \, \, }\textstyle \min \Big\{ \sum _{v\in V} c_ v x_ v ~ \Big|~ x\in {\mathbb N}_+^{V};~ (\forall (u,w)\in E)~ x_ u + x_ w {\, \, \, {\ge }\, \, \, }1\Big\} . \]

Let x^* be an optimal fractional solution, that is, an optimal solution to the linear-program relaxation of this integer program. Let opt be an optimal vertex cover, that is, an optimal solution to the integer program.

The relaxation bounds opt.

How does the cost of x^* relate to the cost of opt? Note that opt is one feasible solution to the linear-program relaxation. Since x^* is the minimum-cost feasible solution, it follows that the cost of opt is at least the cost of x^*.

How can this lower bound be used in an approximation algorithm? The following “rounding” algorithm solves the relaxed problem, then rounds up every variable that is at least 1/2:

  input: Vertex-Cover problem instance
  output: a vertex cover
1. Compute the optimal solution x^* to the linear-program relaxation.
2. For each v\in V, let \tilde x_ v = 1 if x^*_ v \ge 1/2, and \tilde x_ v = 0 otherwise.
3. Return \tilde x.

The algorithm indeed produces a feasible vertex cover \tilde x. (Because, for each edge (u,w), the fractional solution has x^*_ u+x^*_ w\ge 1, so one of x^*_ u or x^*_ w must be at least 1/2, so one of \tilde x_ u or \tilde x_ w must be 1, so one of u or v must be in the cover.)

The algorithm is a 2-approximation algorithm. The vertex cover \tilde x has cost \sum _ v c_ v \tilde x_ v. This is at most twice the cost \sum _ v c_ v x^*_ v of x^* (because each \tilde x_ v \le 2 x^*_ v). Since the cost of opt is at least the cost of x^*, the vertex cover \tilde x has cost at most twice opt.

Randomized rounding

In general, the challenge in rounding is to convert the fractional solution x^* into a feasible integer solution \tilde x without increasing the cost by too much. Naively rounding to the nearest integer (as in the example above) doesn’t work well for most problems. Randomized rounding is generally more useful.

Related

On wikipedia: