Video 10-4: Layering algorithm for Set Cover

0:02 In the next section, we'll look at some more problemsp specific technique for set cover that uh achieves um a different result. I'd say I think it's it's usually stronger. Uh whereas the greedy algorithm from the last section really was very generic for most optimization problems. You can define some version of a greedy method uh to find a solution and it it was not nothing. It was a um a login approximation is not nothing for set cover. uh in particular for this problem is conjectured to be essentially best possible.

0:39 But what what else could we do with a set cover instance? If you um study these uh counter examples or these lower bound families that I've shown you for for the greedy algorithm, it seems to fail on uh instances where the costs are really uh unfair in the sense that uh there's there's some some sets that give you a lot but then have uh relatively cheap costs so that the optimal solution can pick them. uh maybe we should kind of expect something better if the costs are somehow uh less uh less unrealistic. Maybe if a set is larger, it should be more costly. That's the vague intuition here. I mean uh whether you agree with this intuition or not is is maybe not so important. Um a specific way how this this LA last thing could be satisfied is with a size proportional cost where indeed now the cost of a set is exactly some or some constant times its size but because we're we're comparing against optimum you can you might as well say P is one.

1:51 So the cost of a set is the number of elements that it contains. that feels like it should be easier to deal with just because uh it's less easy to cheat in uh the optimal solution to pick some very cheap solution that somehow the greedy algorithm can be tricked into not picking.

2:17 So let's see what we can do. Um it turns out we need another uh uh notion here which is the notion of frequency. So uh the frequency of an element of the universe is just the number of sets that it occurs in. So a very natural thing to look at and we'll keep this uh maximum frequency f without any subscript. That's just the the largest number of sets that any specific element occurs in. We've seen this before just uh I didn't give it the a name there. The vertex cover instances are precisely the set cover instances where f is two and the element occurs in just two sets.

3:02 Now it turns out uh if your costs are size proportional something cute happens. Um if you take all of your sets that's already an f approximation. Uh so it's the most boring of algorithms you just take the trivial solution of picking all sets in the input and uh by the magic of size proportionality uh you can bound the cost by f times the optimum. How does that work? That's a very simple calculation as you can see as a oneline proof. Uh you take the cost of all the sets which is just the sum of all their cost. Now we know this is size proportional. So each of them is P * their size. And now we're just rewriting the sum of the sizes of all the elements in terms of frequency. If I uh sum this over the elements, then I get every element exactly FE times. And uh f was an upper bound for all the fees. And though so that's uh that's basically it because the optimum solution uh has to pay at least or has has to cost at least P * N because it has to pick somehow all the elements and the most costefficient way to do that is to have each element covered just once and then you would have to pay P * N because we know so precisely what the cost of sets are. So uh it's a very very simple observation which by itself is is maybe um not super strong because uh first of all the algorithm is is super boring and it seems that maybe this is this is too restrictive now. Uh requiring that an input has a size proportional cost function is maybe overshooting a bit.

4:52 But we can still turn this into an algorithm by just forcing the cost to be size proportional. And the idea here is um what's then uh called a layering algorithm. Uh we basically pick the smallest proportionality constant to have a cost that is size proportional. Then we um we take the sets that have exactly that cost. uh and for the others we have some residual costs to uh recurse on. So we split the cost the cost of each set is split into a size proportional part and some remainder. So this is just going to be some P times the size. And this one we don't know much about in general but we make sure that it's always non- negative by just picking P small enough. picking P as the smallest uh overall sets. You can always make sure that this is exactly zero for at least one set and greater equal zero for all the sets. If that's all you can do, you're not going to make great progress. But um we'll see how we can uh tie things together at the end uh in terms of this frequency.

6:09 So first of all, the algorithm uh in more structured ways um it finds P as the smallest such ratio. So the smallest proportionality constant for any size proportional cost. Uh then we set Z0 as I just sketched here that's the size proportional part and C1 is the remainder. And uh then we just uh pick for our solution all the sets where this um residue part is exactly zero. So all the sets that have the exact size proportional cost these we pick in our solution for good. So the algorithm is again has a greedy flavor um but it works a bit more on what what greedy means here then we still might have to continue. So we look at all the sets um all the elements in the universe that we get from the sets that we uh just picked all the elements with the size proportional part. If that happens to be all elements we're we're happy and we just return that solution and otherwise uh we can reduce the instance a bit. We can get rid of all the elements that we've already covered. We don't need to pay for those again. And we can uh reduce our attention to all the sets that well uh have any elements left in this in this remaining set.

7:32 Um I think we can also remove all the elements that we've already covered. Uh but these by definition fall out of this because uh U is the universe of all the elements that are completely uh so all all the uh sets that we pick are completely covered completely contained in U and so they can't have an intersection outside of U with S.

8:01 So these are all the remaining sets that are still interesting and then we recursively compute a solution for this for this problem. But importantly here we only put the residual costs in. So the size proportional part is already subtracted and dealt with and we only look at the remaining part and this is important otherwise we may not make progress right. Uh and then the output is just uh the union of these sets.

8:33 Uh so maybe slightly less obvious but if you come from this size proportional idea um this algorithm is is somewhat natural. Uh but how how well does this work?

8:44 Turns out you can show it's an f approximation for f again this maximal frequency and you say hey hold on we already have an f approximation. There it is but that's only if the input was exactly size proportional. Okay, so that's uh very very restricted but we'll use that special case for dealing with the induction basis.

9:08 The proof is by induction over the recursive calls. That shouldn't be surprising. Um and we have to show two things. Namely that the algorithm even computes a valid set cover. I think from the code maybe that's not even 100% obvious. uh and we should show that the cost is at most f times the optimum cost for the induction basis. We're assuming that we we hit the return here in line 8 and then stop which means all of U is covered by the size proportional part and um well we've explicitly checked that we are a set cover so that uh the correctness part A is is fine and for part B we invoke the previous lema because now it is indeed a size proportional instance um if you restrict it to the sets that we picked. So there might be other sets that are more costly, but they're not needed to cover the universe anyway. So you might as well ignore them. And on the restricted uh on the restricted instance, this curly S, I don't know if I can if I can draw a curly S.

10:27 This is just all the elements that we picked. So the curly z0 uh this is size proportional by definition and so the lema must apply and give us an f approximation.

10:45 That's the inductive uh the inductive basis if we return here um what's left is is the inductive step where we have to keep going. Now we use the induction hypothesis on the recursive call. So uh we assume we can assume that C1 what we get back here covers the universe that we recurse on with the cost that we recurse on. So we only get that the cost with respect to C1 of this returned cover is at most f times whatever this the optimum for this weird uh recursive sub instance. Uh so we have to work a bit to put that together. Let's uh suppose we have some optimal set cover with respect to the original problem. So this is our our actual uh target for opt that we uh fight against that's giving us this one. So maybe just to make it clear this is opt um by uh so observe that um all the all the elements that we pick in C 0 they have this cost C1 equal to zero and um the elements here. Uh I mean this what we leave here is uh we we can we can force to apply the lema by making everything size proportional by just looking at Z0 the size proportional part of the cost. So if I take what I pick and the recursively returned set cover then uh with respect to Z0 that's an F approximation because that's forced to be sized proportional.

12:37 Uh so um I can I can uh remember this for later that uh with respect to the Z0 cost our produced solution here at the end is at most f times the optimal solution but evaluate it with the size proportional cost only. Okay, that's also easy. Um now for the the interesting part we have to work a little harder. So first of all we look at uh all the elements in the optimal solution where the uh set is in the recursive call as one was the uh sets that are not completely covered by the size proportional part.

13:33 Um we got to have that this restriction is a set cover for U1 because all all the elements where this I is in the optimal solution but not in C star one they only cover the size proportional part so they can only cover U0 and so U1 was the complement that's what's left to cover these I have to use the sets that are in with indices in this uh curly C star one.

14:12 All right. Which means uh that the cost I pay on this um set C1 that I pick that's by inductive uh inductive hypothesis the optimal solution on this real on this sub problem and this C1 star is some specific solution there. So the optimal solution must be uh can cannot be um worse than this specific solution. This is part of an optimal solution for the entire problem but for the restriction on the on the universe U1 it may not be optimal anymore and sorry this f is the f is missing here. uh all we get from the inductive hypothesis is that we get an f approximation not the optimal solution here. So the f comes from the inductive hypothesis the second part uh the c1 star this is some specific set cover and so it's not more uh it's not cheaper than the optimal solution for that set cover. So, can I Yeah, just for clarity, it's supposed to be a curly S. No, never use curly letters. It's always a pain.

15:41 That's U1. Commas and ones also look the same. Maybe I should write them like this. So uh that's C1 of the curly C star one. That's what we're using here and the F is coming from there. But so also remember this part. If I take um the part of the solution I get recursively and evaluate it under the residue cost C1. That's at most f of what I get for the cost of the part of the optimal solution on on this universe U1. And now we're essentially ready to puzzle everything together. The cost of our solution that we continue that we compute in terms of the the actual cost we care about C can be split into the size proportional part and the residue part. So far so easy. Then um on the residue part we know that all the size proportional sets have resid residue cost zero. So here um I'm uh this this uh C1 of of this set is a sum and I'm leaving out all the terms that are just zero.

17:00 And now I'm using my two uh equations. Let me just copy this one. So that's what we use here. Um each of these parts is now bounded by f*s the respective part with uh of the optimal solution. Here it's the entire optimal solution. uh here it's just the part on U1 as we defined up here. Uh but again um if I include the sets that are from the size proportional part the residue cost is zero. So I can I can include them. They contribute nothing to this sum. And so I can go from here to here. And uh I'm not actually uh well um maybe this is even equal but certainly I can upper bound it by just including more elements here. That's enough doesn't even need an argument. And then we have just rewritten the cost of the optimal solution. So that is that is opt.

18:23 So the overall result is the cost of the solution we produce is at most f times the optimal solution. So the layering algorithm is an f approximation. And note that uh for vertex cover we had f equals 2 always. So we get a two approximation. Yay. We've already had a two approximation for vertex cover. Uh but notice here this is the weighted version. And so uh it is a stronger result. You cannot easily get this with the matching argument that we've used uh last time.

19:03 Okay. And of course um it also works for the general set cover problem. Uh if f is larger the approximation rate is not as good. But it's it's going to be better for all instances where the maximum frequency is below this hn. And um well that's a that's a question that depends on the specific uh application. But I think it's it's uh more realistic to assume that specific elements don't occur a lot of times in different sets. So probably the layering algorithm is usually a stronger approximation.