Randomized rounding

In computer science and operations research, randomized rounding is a widely used approach for designing and analyzing approximation algorithms. Many combinatorial optimization problems are computationally intractable to solve exactly (to optimality). For such problems, randomized rounding can be used to design fast (polynomial time) approximation algorithms—that is, algorithms that are guaranteed to return an approximately optimal solution given any input. The basic idea of randomized rounding is to convert an optimal solution of a relaxation of the problem into an approximately-optimal solution to the original problem. The resulting algorithm is usually analyzed using the probabilistic method.

In computer science and operations research, randomized rounding is a widely used approach for designing and analyzing approximation algorithms. Many combinatorial optimization problems are computationally intractable to solve exactly (to optimality). For such problems, randomized rounding can be used to design fast (polynomial time) approximation algorithms—that is, algorithms that are guaranteed to return an approximately optimal solution given any input. The basic idea of randomized rounding is to convert an optimal solution of a relaxation of the problem into an approximately-optimal solution to the original problem. The resulting algorithm is usually analyzed using the probabilistic method. is as small as possible. Note that any set cover \mathcal C for \mathcal S gives a feasible solution x (where x_s=1 for s\in\mathcal C , x_s=0 otherwise). The cost of this \mathcal C equals the cost of x , that is, \sum_{s\in\mathcal C} c(s) = \sum_{s\in\mathcal S} c(s) x_s. In other words, the linear program LP is a relaxation of the given set-cover problem. Since x^* has minimum cost among feasible solutions to the LP, the cost of x^* is a lower bound on the cost of the optimal set cover. For each set s\in\mathcal S in turn, take x'_s = 1 with probability \min(1,x^*_s) , otherwise take x'_s = 0 . With this rounding scheme, the expected cost of the chosen sets is at most \sum_s c(s) x^*_s , the cost of the fractional cover. This is good. Unfortunately the coverage is not good. When the variables x^*_s are small, the probability that an element e is not covered is about \prod_{s\ni e} 1-x^*_s \approx \prod_{s\ni e} \exp(-x^*_s) = \exp\Big(-\sum_{s\ni e}x^*_s\Big) \approx \exp(-1). So only a constant fraction of the elements will be covered in expectation. To make x' cover every element with high probability, the standard rounding scheme first scales up the rounding probabilities by an appropriate factor \lambda > 1 . Here is the standard rounding scheme: Fix a parameter \lambda \ge 1 . For each set s\in\mathcal S in turn, take x'_s = 1 with probability \min(\lambda x^*_s, 1) , otherwise take x'_s = 0 . Scaling the probabilities up by \lambda increases the expected cost by \lambda , but makes coverage of all elements likely. The idea is to choose \lambda as small as possible so that all elements are provably covered with non-zero probability. Here is a detailed analysis. ---- Fix \lambda = \ln (2|\mathcal U|) . With positive probability, the rounding scheme returns a set cover x' of cost at most 2\ln(2|\mathcal U|) c\cdot x^* (and thus of cost O(\log |\mathcal U|) times the cost of the optimal set cover). (Note: with care the O(\log |\mathcal U|) can be reduced to \ln(|\mathcal U|)+O(\log\log|\mathcal U|) .) is at most \sum_s c(s)\lambda x_s^*=\lambda c\cdot x^* . Thus, by Markov's inequality, the probability of the first bad event above is at most 1/2 . For the remaining bad events (one for each element e ), note that, since \sum_{s\ni e} x^*_s \ge 1 for any given element e , the probability that e is not covered is \begin{align} \prod_{s\ni e} \big(1-\min(\lambda x^*_s,1) \big) & (This uses the inequality 1+z\le e^z , which is strict for z \ne 0 .) Thus, for each of the |\mathcal U| elements, the probability that the element is not covered is less than 1/(2\mathcal U) . By the union bound, the probability that one of the 1+|\mathcal U| bad events happens is less than 1/2 + |\mathcal U|/(2\mathcal U)=1 . Thus, with positive probability there are no bad events and x' is a set cover of cost at most 2\lambda c\cdot x^* . QED F = \frac{c\cdot x'}{2\lambda c\cdot x^*} + |\mathcal U^{(m)}| , where \mathcal U^{(m)}= \Big\{ e : \prod_{s\ni e} (1-x'_s) = 1\Big\} is the set of elements left uncovered at the end. The random variable F may appear a bit mysterious, but it mirrors the probabilistic proof in a systematic way. The first term in F comes from applying Markov's inequality to bound the probability of the first bad event (the cost is too high). It contributes at least 1 to F if the cost of x' is too high. The second term counts the number of bad events of the second kind (uncovered elements). It contributes at least 1 to F if x' leaves any element uncovered. Thus, in any outcome where F is less than 1, x' must cover all the elements and have cost meeting the desired bound from the lemma. In short, if the rounding step fails, then F \ge 1 . This implies (by Markov's inequality) that E[F] is an upper bound on the probability of failure. Note that the argument above is implicit already in the proof of the lemma, which also shows by calculation that E[F] . To apply the method of conditional probabilities, we need to extend the argument to bound the conditional probability of failure as the rounding step proceeds. Usually, this can be done in a systematic way, although it can be technically tedious. So, what about the conditional probability of failure as the rounding step iterates through the sets? Since F \ge 1 in any outcome where the rounding step fails, by Markov's inequality, the conditional probability of failure is at most the conditional expectation of F . Next we calculate the conditional expectation of F , much as we calculated the unconditioned expectation of F in the original proof. Consider the state of the rounding process at the end of some iteration t . Let S^{(t)} denote the sets considered so far (the first t sets in \mathcal S ). Let x^{(t)} denote the (partially assigned) vector x' (so x^{(t)}_s is determined only if s\in S^{(t)} ). For each set s\not\in S^{(t)} , let p_s = \min(\lambda x^*_s, 1) denote the probability with which x'_s will be set to 1. Let \mathcal U^{(t)} contain the not-yet-covered elements. Then the conditional expectation of F , given the choices made so far, that is, given x^{(t)} , is E[F | x^{(t)}] ~=~ \frac{\sum_{s\in S^{(t)}} c(s) x'_s + \sum_{s\not\in S^{(t)}} c(s) p_s}{2\lambda c\cdot x^*} ~+~ \sum_{e\in \mathcal U^{(t)}}\prod_{s\not\in S^{(t)}, s\ni e} (1-p_s). Note that E[F | x^{(t)}] is determined only after iteration t . (where m=|\mathcal S| ). In the t th iteration, how can the algorithm set x'_{s'} to ensure that E[F|x^{(t)}] \le E[F|S^{(t-1)}] ? It turns out that it can simply set x'_{s'} so as to minimize the resulting value of E[F|x^{(t)}] . To see why, focus on the point in time when iteration t starts. At that time, E[F|x^{(t-1)}] is determined, but E[F|x^{(t)}] is not yet determined --- it can take two possible values depending on how x'_{s'} is set in iteration t . Let E^{(t-1)} denote the value of E[F|x'^{(t-1)}] . Let E^{(t)}_0 and E^{(t)}_1 , denote the two possible values of E[F|x^{(t)}] , depending on whether x'_{s'} is set to 0, or 1, respectively. By the definition of conditional expectation, E^{(t-1)} ~=~ \Pr[x'_{s'}=0] E^{(t)}_0 + \Pr[x'_{s'}=1] E^{(t)}_1. Since a weighted average of two quantities is always at least the minimum of those two quantities, it follows that E^{(t-1)} ~\ge~ \min( E^{(t)}_0, E^{(t)}_1 ). Thus, setting x'_{s'} so as to minimize the resulting value of E[F | x^{(t)}] will guarantee that E[F | x^{(t)}] \le E[F | x^{(t-1)}] . This is what the algorithm will do. In detail, what does this mean? Considered as a function of x'_{s'} (with all other quantities fixed) E[F | x^{(t)}] is a linear function of x'_{s'} , and the coefficient of x'_{s'} in that function is \frac{c_{s'}}{2\lambda c\cdot x^*} ~-~ \sum_{e\in s'\cap \mathcal U_{t-1}}\prod_{s\not\in S^{(t)}, s\ni e} (1-p_s). Thus, the algorithm should set x'_{s'} to 0 if this expression is positive, and 1 otherwise. This gives the following algorithm.

Further reading

Text derived from https://en.wikipedia.org/w/index.php?oldid=1364801195 under CC BY-SA 4.0; modifications have been made.