Video 11-3: Randomized Rounding

0:01 In the next section, we'll look at a second way to use the fractional solution and round it somehow. Um, and we bring back randomization here, which is um um yields yields different performance guarantees. I guess it's not obvious which one is stronger in general. Uh the idea behind this is especially if the values like in our set cover case are between zero and one you could pretend they're probabilities or intuitively if the fractional solution includes a set uh gives a set a certain value you could say this is a a probability that you want to take that set and so you can just do that and the cool thing about that is that if you take the expected cost of the sets you get of the collection you get that'll be exactly the optimal uh fractions uh objective value just by definition. Um I guess assuming here uh that we have numbers between zero and one and so that sounds uh maybe too good to be true because we we know we can't usually achieve the value of the of the LP and indeed most of the time if you just randomly pick the collection like this you're not going to get a feasible solution for the integral problem. Uh but uh we'll we'll see that you can often still get something out of this idea.

1:26 Um and here if you think in the context of set cover again if some element in the universe occurs in a certain number of sets then the probability that it is covered is one minus the probability that it is not and the probability that it is not covered is the probability that for all the sets where it occurs we don't pick that set right um and that you can write because we've picked the probabilities is just to be these variables for the sets. It's one minus the product of one minus the the variable. Now that sounds maybe not like you could do much but you can bound it. um such a product is is always minimized um because this kind of convexity argument is minimized when you have the same value for all the xjs and uh in particular here because they're between zero and one over fe is um because you have the constraints from so you're using convexity and the the constraint that all These have to sum to at least one uh to bound it like this. Then this is our um seen seen that inequality many times before. This is uh in the limit goes to e and for any finite value is is below um kind of the repeated interest thing.

3:02 So you can you can lower bound the probability that a specific element is not covered if you just pick a random set cover uh candidate like this by at least some constant. It's not uh is not with high probability or anything but is also not zero. And so if you repeatedly uh draw such set cover candidates um this this question turns into a kind of a coupon collector scenario. If you keep uh the assumption is that you keep all the sets that you've ever chosen and uh just um keep adding to your candidate set then if you do that for roughly uh login repetitions you should cover all the sets. Then you've collected all your coupons and it's curious that the same harmonic number pops up that turn if you remember that was the approximation ratio of the greedy set cover algorithm. Um the reason to look at it again is that the methodology here is is more general than set cover. So how can we make this work? uh in particular we're uh we're using this randomized rounding from before and repeat it many times. So here r is the number of of repetitions.

4:24 So you see this is the outer loop but we're computing one candidate set. So we we do our iterations but then for um uh for each of the iterations we go through all the possible sets in our our input and add uh this set with a certain probability to this candidate set CI and at the end we return their union. So anything any set that was picked in any of the R it iterations is going to be part of the final solution from this handwavy argument. Maybe we should expect some uh logarithmic number of repetitions to be the right choice. And well it'll it turns out to get the numbers right you want to use a slightly bigger number than that. So it's it's not ln it's ln n plus a constant right and if you do that then uh this algorithm produces a feasible set cover that's uh indeed a set cover and deserves this name with probability at least three quarters and we've done most of the work for the proof. um the probability that a certain element is not covered was bounded by this uh 1 / e. We've argued about the counter probability previously but uh it's more convenient to write it like this because this is the probability that a single element in the universe is not covered.

6:00 To get a bound that none of the elements is not covered, we take the union bound over all of those elements. So the probability um this was for one iteration. If we keep repeating this r times then we get the r power of this um that it's not covered in all of the repetitions. So this goes down a lot with r and the union bound then is that the result is not a set cover. It's just the factor n um times this. So if you set r to uh natural log of 4n and this works out to exactly 1 over4. Okay.

6:48 Now this is the probability that we get any set cover. Um the other question is how good will it be and the expected cost is what we can bound. If we produce a set cover with this previous uh algorithm, then the expected cost it has is r times the optimal solution.

7:07 So we essentially pay the same same factor here. Um if that's the case, then this is only about the expected cost. We can as always use marov's inequality to turn that into an a success probability when we scale up the expectation a bit. So in particular four times the expected size the expected value will give you a probability of one quarter to be above that. That's more what we're going to use on the next slide. Uh but let's first prove this in the general sense. Uh our algorithm picks the final solution as the union of our repeatedly chosen things. These are all identically distributed and independent. uh for the cost the cost of the final result is at most the sum of the cost of all those elements summed up. It'll probably be a bit less because we repeatedly draw some sets but it's hard to analyze. So we'll just upper bound it generously. Then we use linearity of expectations and move that in. And because these are r identical repetitions each time the expectation is as as we've calculated before the optimal LP solution. And so you get this R times uh as in the claim.

8:26 Okay. Now this is not a randomized uh this is not an an approximation algorithm in the way we defined it because it sometimes returns a solution that's not actually a solution. It's not even feasible. uh in in this case that's easy to fix by uh if the algorithm fails just taking all sets. So you run your randomized uh rounding. If the output is garbage then uh you output all of the sets otherwise you keep it. And uh with that you can show that this is a a randomized four login approximation for set cover and we've basically done that. So you just have to prove that uh with probability 1/2 right this was the definition randomized blah blah approximation means with probability 1/2 the approximation ratio is below this uh bound and for that um we have to bound how often we return the entire set because we cannot say much about its quality there. So the probability that C is not a set cover which means we return something of bad quality or that um it is a set cover but it actually is of poor quality itself uh in terms of the cost. That's um the the union of two events. I can upper bound that union bound by the sum of the probabilities and both of these we've just uh bounded by the previous lemas. This was that it the algorithm doesn't output a set cover and this was the mark of inequality from the previous slide. So in total with probability 1/2 we get something that's at least as good as that and with probability one we get something feasible.