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.

  • $\begingroup$ your first paragraph is very weird. the exponential running time of simplex is not a bottleneck at all here. the bottleneck is that many problems require exponential number of constraints in order to make sure that all optimal solutions are integral, so we relax by dropping all but a polynomial number of constraints. also your questions has no single answer: for each problem we need a different argument to make sure rounding gives a feasible solution. the best example we have of a somewhat universal rounding technique is Raghavendra's SDP rounding $\endgroup$ – Sasho Nikolov Nov 28 '12 at 0:55
  • $\begingroup$ @SashoNikolov, I suppose the first paragraph is awkward. It was meant to merely introduce some motivation for approximation methods regarding ILPs. But if it is factually incorrect, I (or someone with more understanding) can edit. Based on current responses it seems that there will be no "catch all" approach to rounding. However, common approaches should be fine for an answer. $\endgroup$ – Nicholas Mancuso Nov 28 '12 at 1:51
  • $\begingroup$ every single statement is correct but it just misses the point. you don't need to worry about the simplex method here, since there are polytime LP algorithms. the problem is that while every NP optimization problem can be formulated as a linear program with integer solutions, for NP-complete problems no such LP will have a concise representation, so we are forced to drop all but a poly number of constraints. $\endgroup$ – Sasho Nikolov Nov 29 '12 at 23:31
  • $\begingroup$ @SashoNikolov, (I think) I have edited it accordingly. $\endgroup$ – Nicholas Mancuso Nov 30 '12 at 4:10

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.


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

  • $\begingroup$ Also regarding set cover, if can show your rounding scheme has constant probability ($\leq 1/2$) that a constraint will be violated you could just re-run it some constant number of times until things are fine. This is shown for set-cover in Vazirani's book. $\endgroup$ – Nicholas Mancuso Mar 17 '13 at 21:47
  • $\begingroup$ @AJed - Can you give me the source for the reference? Its kind of hard to read :), and I'd like to access the original book/paper/lecture note if possible! thanks! $\endgroup$ – TCSGrad Aug 14 '14 at 23:04
  • $\begingroup$ I really forgot that book. But have a look at Vazirani's book (approximation algorithms). It s a very important reference to have. $\endgroup$ – AJed Aug 15 '14 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.