Video 10-3: Greedy Set Cover

0:03 After introducing what uh approximation algorithms are and seeing a first example on the vertex cover problem, we'll start seeing a few more interesting techniques to design such algorithms and we'll do so um mostly for now on the set cover problem uh which is formally defined here. So it's um we're given a a universe. We'll assume here that there's n things in the universe. uh it's often convenient to take the first n integers but that's uh not we'll not be too strict about that and then the input consists mainly of sets uh subsets of this universe so a collection of sets from elements in the universe and in the general version these sets have certain costs uh that we can specify then solutions are such that uh collections of subsets or here formally the the output is a collection of indices. So that if I take all the elements with indices in that set curly C then I get as the union all of the universe back.

1:08 So I have to cover the whole universe by making a selection from the sets I'm given and uh the cost of such a selection is just the sum of all the sets uh costs and that we want to minimize. Um clearly we would want for an an input to make sense that at least uh if I take all of the k sets that they cover u so um otherwise the problem is not feasible then certainly we want to minimize because I can always take all sets and we assume the costs are uh weakly positive say uh there's a restricted version the um can either call it the cardality version or the unweighted set cover version. Um where I guess the number that's uh that's a weird version. Uh the cost should be one for each set. We just count how many sets we take. Uh I think I was jumping ahead of myself here. Uh unweighted set cover is a strict generalization of vertex cover where we have the additional property. So as I mentioned yesterday, if you have some graph uh let's maybe draw a short example think about the problem could be uh this. So uh a vertex cover has to cover all the edges.

2:35 So the edges become this uh elements in the universe and uh any specific vertex that I pick covers a certain subset of the edges namely its neighborhood or the uh I should say the the edges incident at that vertex. So if you have um a vertex cover instance it is a set cover instance but it's a special set cover instance namely every edge occurs in exactly the uh sets of its two end points. So it's not a a completely general set cover instance but one where um every element of the universe occurs in exactly two sets. And we normally think of vertex cover as being unweighted. So we just count how many uh vertices we have to pick. But of course you could define a vert a weighted version of vertex cover.

3:26 Um, if you want to have a a generalization that stays in the realm of graphs, you could say we were going to hyper graphs in a hyperraph edges become hyper edges or just any subsets of vertices. And then clearly you can always map an instance of set cover uh into a hyperraph where you have the vertices for the elements of the universe. One, two, three, four, five, six. And then you can draw uh say we have a set that contains 1 three and four. So that could be si one 3 4 and you just draw a hyper edge around those. And if you have a bunch of those hyper edges, maybe there's a few ordinary edges as well. And then you have a few of those. Then you can ask what's the smallest number of them that I have to pick to cover all the vertices as sorry this smallest. Uh I guess these are these are the hyper edges. So um am I confusing the picture now?

4:32 Yeah. each of these um sets corresponds to some uh some vertex that's contained in all of those. So I didn't draw the vertices. Uh I should have should have drawn this differently.

5:03 The hyper edges become the vertices. Uh, is there a nice way to draw this directly from the sets? Okay, you know what? Let's let's leave it. Uh, I don't know if I can put it in a nicer picture next time. Uh either way it's it's a generalization of vertex cover and you can you can formally define it as a hyperraph but it's it's not helpful uh helpful by much. Um we're mostly using this is to illustrate things but we'll also see that set cover can represent some other problems in terms of reduction. If you think about uh optimization problems and uh approximate solutions for them, a natural approach is to try some simple myopic greedy uristic which you should usually get some feasible solution from. But often times you don't get a guarantee how good it is. And so it's a natural approach to say let's start with a somewhat simple greedy algorithm and see if it is an approximation algorithm. And so we can do that for set cover as well.

6:16 Um the natural notion of greedy here uh for the fully general problem if you want to take cost into account I guess if you think about it for a moment is that you want the best set in terms of cost per new element. You uh you may have some collection of sets already and then there's all the sets that you haven't picked yet uh where you can choose which one to pick next. Uh but some sets are are more valuable than others because they give you a lot of new elements that you haven't covered yet and that you will eventually have to cover. Um and they do this at different costs. So it's it's not so useful to take an expensive set that only gives you a single new element. If you could for the same cost cover several. I think that's that's the intuition. Um the intuition behind that is is quite clear. You want the cost for each element that you cover to be small because you have to cover the same number n in total at uh in any solution.

7:13 Uh so a formal way to to um greedily pick always the next best set in terms of the cost per new item ratio is is spelled out here. We start with having nothing covered. C is the elements that we have already covered and curly C is the indices of the sets that we used for that. So at the end the curly C is the actual solution but we need to keep track of how many elements we still have to cover. So as long as we haven't covered everything we find a set that minimizes this ratio the cost of the set divided by how many elements does this add to the covered elements. So the uh sets as I subtracted all the elements that uh we have already covered with other sets and uh we find the one that minimizes this. That's the one we pick next. It's a greedy algorithm. We never take a step back and we keep doing this until we've covered all elements. Uh here again I'm I'm assuming the instance is feasible, right? Otherwise this Y loop might never terminate.

8:24 I think all always in the following will we'll make this assumption that if I take everything then I get the universe back. Uh there's a few um annotations there that are kind of uh not part of the algorithm but are useful for the analysis. uh we can the the while loop is not a for loop with specific iterations but of course you can speak about the i iteration just the the way it's run and we uh keep track of uh the price at which we covered certain elements. So alpha i is the uh cost per new item ratio of the set that we picked in the i iteration. And for all the elements that we now gained in the covered elements c for those elements we set the price at which we have covered them to alpha i. And so you can immediate observation is that this price over time and the alpha i can only increase uh because we're um we're taking away elements that could have reduced the cost and we're always picking the best current one.

9:38 Now the the key lama to understand how well this algorithm works is is this price lema that tells us something about say the worst case of these prices for specific elements. Uh and for that um we rename the elements in the universe so that they appear in the order that they're included here in the set C of covered elements. So this is what this order is referring to.

10:05 And um then it says uh the elements indeed become more costly over time. At least we have an upper bound for how much uh we have to pay to add this element to our u to our set of covered elements. And it says in this algorithm it's upperbounded by the cost of the optimal solution. But here this uh op refers to the entire set covered uh and it's divided by some term that uh when I gets bigger becomes uh smaller. So the overall upper bound here gets worse. Uh let's let's prove this is a is a simple proof but I think it's insightful to to do it briefly. Um uh consider the time when we cover this J element. Now we usually cover those in in batches of including an an entire set essentially in one in one time step gives you several elements but we uh logically separate that into covering one element after the other.

11:04 So uh before this element is included we've uh had obviously j minus one elements covered because that is the j one. So there were n minus j minus one elements left uncovered.

11:19 uh we'll use this complement set uh going forward. Now if you take um any optimal set cover curly C star uh that one even if I'm partway through my algorithm I could always uh say uh okay I've made some some uh initial decisions into my curly C but for now uh I'm just going to keep it as it is and add the optimal solution on top. Certainly the optimal solution has to cover these remaining uncovered elements because it covers everything and it does so at cost at most opt. It seems like a very crude argument. Um but we'll see it's it's uh essentially tight. So it means that there must be some some set and indeed it could be our our set that we here pick in the minimization uh which is I guess in the optimal solution um but not yet covered not yet picked in our solution where you can bound this uh this cost per new item ratio and um we can uh we can upper bound this by the cost of the optimal solution divided by the elements that are left to cover.

12:34 Uh because assume towards the contradiction this wasn't the case. There was no such set left with such a low cost per new item ratio. Well then uh if you uh if if you take this uh average cost per element and sum it over all the remaining elements it means that you would need strictly more than op divided by C bar uh cost um for well if if you sum it up over all those C bar elements you would require strictly more than opt to cover just the remaining elements but the optimal solution covers all of them at cost most opt so that's a contradiction So we always find a set si star where the cost per new item ratio is is at most opiv divided bar c and um that I'm just inserting. So it's uh it's a relatively crude argument. Uh we're just saying at at any point in time I could have continued with the full optimal solution and that gives me a a bound of how much I have to pay per element.

13:41 uh if you plug this uh if you put this together you get an approximation ratio for the set cover problem and what we get is an hn approximation. So n hn is the harmonic number and you you will remember maybe uh popped up in this module a few times that this is uh you can write it asmtoically as the natural log of n plus um some infamous uh constant and then a lower order term that's uh the oiler musher constant 0.57 something but the basic message is it's by and large natural log of So this is is growing with n, right? It's um it's not a constant factor approximation and um it's maybe not so great. But let's first prove it before we uh uh dismiss the uh the result. So we um we want to bound the cost of our solution that the greedy algorithm finds. That's um the cost is the sum of all the costs of the sets that we pick. And I can rewrite that as the price at which I included all the elements. That's just um here I'm I'm summing over the cost of the of the sets. Here I'm summing over the elements. Now some elements are covered by multiple sets but the price is defined such that it only takes the new elements into account. So when I cover some some elements several times, right? So here's my my universe.

15:15 Say I'm first covering these elements. They the three of them share the cost of this set. If the next set is taking these elements, only those two new elements share the cost of this new set. So, uh it's just rewriting the the sum over the costs of all the sets that I pick. Um and now of course we use our price lema to upperbound the price. Uh that's a simple calculation then and you pull out up which is a constant factor. You're left with that sum and that's exactly the nth harmonic number. So it's a very simple analysis. No uh no fancy uh math needed here. Uh but I really want to stress again this was just the simplest greedy algorithm that um if for the for the uh weighted version of set cover it's the most natural thing to try. Always pick the element that gives you on an amortized cost per element that you gain uh the best next step.

16:22 But really a an approximation guarantee that grows with n is not so great um could be a large factor if the input is big. Unfortunately this is essentially the best we can hope for. Again um in the worst case you can consider for example um the following instance. Uh it's a a star graph.

16:49 The worst case instance is indeed a vertex cover instance where every element in the universe occurs in at most two sets. Um but I need here a weighted version of vertex cover and the weights are um chosen so that this this fails. So I'm I'm putting a weight of 1 plus epsilon here on this center of the star and then I'm putting uh harmonically increasing weights on the elements around the star until I have one.

17:27 And so what what happens in the greedy algorithm is uh initially um this vertex looks uh this this singleton set that just gives me this one edge. It looks really attractive because it's very cost it's very cheap whereas um this other guy here would give me um n edges but at the price of uh 1 plus epsilon. So the cost per element for the center initially is 1 plus epsilon divided by n. Whereas the leaf has 1 / n. So that wins. So I'm going to pick that leaf in the greedy algorithm. And then the same thing happens again. I'm uh I have one less element to cover. So I have 1 + epsilon / n minus one. in the next step.

18:27 And so again, this uh leaf appears cheaper to the greedy algorithm. And so it picks all the leaves around there, all the end sets, whereas I could have picked the center at the start. So the optimal cost is one plus epsilon, which is obvious here. Uh but the greedy set cover decides to pick all the leaves around there.

18:57 Uh you can even boost this construction for the unweighted vertex cover problem. Um that's that's more tricky and I don't don't think that's super insightful, but it's a nice puzzle to think about. Uh you can show even even if you take the unweighted um vertex cover, then the the greedy algorithm as we've shown it uh is not going to work well. Of course, you can do better on vertex cover. We've seen the approach with matchings last time. But if you uh so this is bore greedy, you can show that this this specific algorithm uh is not not doing so well. Um there this kind of logarithmic growth seems seems uh inherent.