Randomized Rounding of Solutions to Linear Programs

Question

Integer linear programming (ILP) is an incredibly powerful tool in combinatorial optimization. If we can formulate some problem as an instance of an ILP then solvers are guaranteed to find the global optimum. However, enforcing integral solutions has runtime that is exponential in the worst case. To cope with this barrier, several approximation methods related to ILPs can be used,

• Primal-Dual Schema
• Randomized Rounding

The Primal-Dual Schema is a versatile method that gives us a "packaged" way to come up with a greedy algorithm and prove its approximation bounds using the relaxed dual LP. Resulting combinatorial algorithms tend to be very fast and perform quite well in practice. However its relation to linear programming is closer tied to the analysis. Further because of this analysis, we can easily show that constraints are not violated.

Randomized rounding takes a different approach and solves the relaxed LP (using interior-point or ellipsoid methods) and rounds variables according to some probability distribution. If approximation bounds can be proven this method, like the Primal-Dual schema, is quite useful. However, one portion is not quite clear to me:

How do randomized rounding schemes show that constraints are not violated?

It would appear that naively flipping a coin, while resulting in a 0-1 solution, could violate constraints! Any help illuminating this issue would be appreciated. Thank you.

Answer 1

Of course, if you round, you have to verify that rounding preserves feasibility.

Let us for example consider the relaxed VERTEX-COVER LP formulation. $$ \begin{array}{lll} \text{min} & \sum_{v\in V}c(v)x_v & \\ \text{s.t.} &x_u+x_v\ge1, & \quad (u,v)\in E \\ &x_v\ge 0. & \quad v\in V \end{array} $$

It is known that the solution to this problem is half-integral, i.e., each variable is either $0$, $1$, or $1/2$. The rounding scheme works as follows, whenever your solution contains $x_v=1/2$ you round up and set $x_v=1$. The constraints of the ILP were $$ \begin{array}{lll} &x_u+x_v\ge1, & \quad (u,v)\in E \\ &x_v \in \{0,1\}. & \quad v\in V \end{array} $$ Both constraints are fulfilled after the rounding. And you have a nice 2-approximation.

Answer 2

Yes, this is confusing in the first sight.

I see it like this:

step1) generate a linear program solution [all the linear program constraints are satisfied in here - except that it is not Integer solution],

step2) randomize it (change the value to integers according to a probability distribution you select),

step3) make sure the randomized solution is correct (by making few changes on it).

For example, in the set-cover. After randomization, you may end up with a collection of sets that are not necessarily a set cover. In this case, you should add some sets that cover all the uncovered elements (and thus, you get the solution you want).

To avoid such big changes in the randomized linear program solution, follow a randomized rounding scheme that guarantees with high probability that a solution is found after rounding (i.e. you will not need to do many changes in the linear program solution in order to get what you want).

See this for a reference: 1