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.)

Click for background material…

Modeling problems as linear programs.

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 ? Note that is one feasible solution to the linear-program relaxation. Since $x^*$ is the minimum-cost feasible solution, it follows that the cost of 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 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.

On wikipedia:

Notes on algorithms

Lecture notes on algorithms

rounding an LP relaxation

Trivial example: vertex cover

Randomized rounding

Related