# rounding an LP relaxation

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

1. Model your problem as an integer linear program.

2. Solve its linear program relaxation.

3. Somehow round the solution of the relaxed problem to get a solution 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 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 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 relate to the cost of opt? Note that opt is one feasible solution to the linear-program relaxation. Since is the minimum-cost feasible solution, it follows that the cost of opt is at least the cost of .

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 to the linear-program relaxation. 2. For each , let if , and otherwise. 3. Return .

The algorithm indeed produces a feasible vertex cover . (Because, for each edge , the fractional solution has , so one of or must be at least 1/2, so one of or must be 1, so one of or must be in the cover.)

The algorithm is a 2-approximation algorithm. The vertex cover has cost . This is at most twice the cost of (because each ). Since the cost of opt is at least the cost of , the vertex cover has cost at most twice opt.

# Randomized rounding

In general, the challenge in rounding is to convert the fractional solution into a feasible integer solution 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: