[Solved]: Randomized Rounding of Solutions to Linear Programs

ignougroup
Problem Detail: 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.

Asked By : Nicholas Mancuso

Answered By : A.Schulz

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_{vin V}c(v)x_v & text{s.t.} &x_u+x_vge1, & quad (u,v)in E &x_vge 0. & quad vin 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_vge1, & quad (u,v)in E &x_v in {0,1}. & quad vin V end{array} $$ Both constraints are fulfilled after the rounding. And you have a nice 2-approximation.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6941