[MUSIC] The algorithm we have so far is great in terms of cost, it's average cost is at most opt. But it's not so good in terms of coverage, it's got a set cover. On average it only covers about 63% of the ailments. So what are we going to do? The idea is simple, iterate. Repeat taking steps until you get a natural set cover. And so here is a randomized rounding algorithm for set cover. Let n denote the number of elements in a set cover. We will repeat ln(n)+3 times the following operation. For each set S, we put S in our cover with probability x(S) if of course it's not there already. Why +3? Because e cubed is about 20. So what do we do with this? Let's see. What does this mean? The cost in expectation will be at most (ln(n) +3)OPT. Very good. This will give us a log(n) approximation if it's a set cover. What about correctness? What is the probability that the output is a cover? It's one minus the probability that it's not a cover. What is the probability that it's not a cover? It's the probability that some element there exists an element that is not covered. The probability that there exists an element is at most a sum of the probabilities, because probability of A or B is at most probability of A plus probability of B, even if A and B are not independent. This is a general fact. So the probability that the output is not a cover is at most the sum over every element E Of the probability that e is not covered. What is that quantity? What is the probability that e is not covered? For one element e, fixed one element e, and for one iteration, let's look at one iteration of the for loop. We know from previous analysis that the probability that e is not covered, is at most one over e. If you put all iterations together, they are all independent. So the probability that e is not covered, is the probability that every iteration is not covered. This is a product of the probabilities, because all these events are independent from one iteration to the next. And so each of them can be bounded by 1 over e. It's the product there are log n plus 3 terms, so that at most, 1 over e to the log n plus 3. What is that? 1/e cubed n. About 1 over 20n. Putting it together, the sum over every element e of the probability that the element is not covered, is at most n times 1/e cubed n, which is less than 0.05. Therefore the output is a correct set cover with probability at least 95%. In other words, what we have proved is that by doing randomized rounding and iterating, iterated randomized rounding, gives us a collection of sets that is a set cover. With probability at least 95% and with cost is on average, at most log n plus 3 times opt. We're almost there. We have something which is essentially a randomized algorithm for set cover, for almost set cover, for something that 95% of the time is the set cover. In the next part, what we will see is how to transform this into an algorithm that always returns a set cover.