A simple example of computing an approximate solution by rounding the solution to a linear-program relaxation.
The basic paradigm:
Model your problem as an integer linear program.
Solve its linear program relaxation.
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
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.
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.
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.