Video 11-6: Dual Fitting

0:03 In the next two sections, we'll make uh further use of the duality theory in approximation algorithms. Uh and the first one, so there's there's two separate techniques. The first one is is called dual fitting, which is if you want rather an analysis technique that uses duality as opposed to an algorithm that directly uses it. And we'll see that on the on the example of set cover as as in the past. Uh the basic idea is uh is this that um we have some algorithm often it's an algorithm that already existed before we even thought about duality and the algorithm maintains uh a candidate solution that is a a feasible solution. So it's um feasible for the ILP I should say it's integral and feasible for the primal solution. So it in set cover it has to be a set cover. Um but then uh or at at the end at least it has to be a set cover. Uh but the guarantee for its bound we can analyze by taking the the bound the the cost of X in the primal LP and somehow derive from that um a dual uh dual set of variables. Um they may not immediately be feasible but we can modify this uh set of dual variables. So these these values for the dual variables by scaling them down and then that scaled down version is feasible.

1:36 And so you can use this as follows. The optimal actual value is uh what you're looking for. That's where we're still in this realm of doing the minimization ctx subject to ax greater equal b x greater equal zero. That's our primal LP. And here of course would be in uh n to the n.

2:05 Um if you have the ILP, so opt denotes the optimal objective value of the integral best integral solution. Since it's a minimization problem, that's uh only going to get better if you loosen the integrality constraints to be just x greater equal zero. Uh, come on. We have this easy option. So, let me just get the the two LPS written up separately.

2:42 So, that's our ILP and that's our uh primal LP. So, the optimal objective value of this one is going to be better than this one. That's uh CT for some XAR, whatever that is. And by strong duality that's the same as bty for some optimal dual uh variable. So the dual will be would be this one and then that's the optimal you could you could say that's opt uh duel and we'll we'll make sure that uh our y the I know is is a bit abstract and unclear. It it'll be more clear on the concrete example. Uh you somehow get to these dual variables from your uh algorithm. And if you scale them down, if you divide them component-wise by some uh scalar delta, then that is a feasible dually feasible solution, which means its objective value is going to be at least at most at most the optimal value for that LP. So you can continue this inequality chain. And then of course uh you can pull this delta out. So if you re rewrite this um for your concrete solution it's going to be uh still less than your that's weak duality here.

4:28 And here you get this bty. If you pull delta to the other side, you get that this is at most uh delta times the optimal objective value. So you get an an an upper bound for how bad your cost for this algorithm will be. And it all depends on how much you have to scale down this dual variables uh to make them dually feasible. That's the u the key question you have to ask. And so on our concrete example um the set cover problem uh you'll remember hopefully is is a collection of sets over some universe and we'll we'll heavily use this um notation B of E is the set of all indices of sets where this specific element of the universe occurs. So an notation is somehow uh suggesting that this has to do with graphs. And of course if you think about the special case of set cover where it's a vertex cover. The elements of the universe are the edges of a graph. And then V of E would just be all the uh end points of an edge. Uh just the two vertices. But in in general um for set cover this could be a larger set right.

5:46 uh then we can write uh the set cover ILP or LP as we want to minimize the total cost. We've seen this before. XJ encodes whether the set is chosen in the solution or not. And we think of this as being zero or one in the LP. Of course, it could be fractional. We multiply it with the cost of that set. What's the site condition? It's it it has to be a set cover which means for every um for every uh we have a constraint for every element in the universe and we sum over all the sets that contain this element and then in in total they have to cover it and in the integral case that's a set cover in the fractional case it's a a fractional set cover okay uh you can dualize the set cover um LP then you get this one just by applying uh the rules or the intuition from last time. Um so you have some uh variables y and often times so the the way to think about this is that you go from primal to dual mechanically.

7:00 You just follow the rules. But then it often helps to take a step back and look and uh stare for a while at this dual LP and see if it tells you something intuitively because often it does. We've seen for vertex cover this was particularly clean in that it gave you just the maximum matching. Uh here for general set cover is is a little a little less clean maybe. um you get something you want to maximize some some uh y e uh a value for each element in the universe and what's the uh constraints they say if you sum up all the elements in some specific set then you can't exhaust the cost of that set so you could uh c could nicely stand for cost or for capacity um so you could say that this uh the universe elements are some some goods and you want to pack as much of that good as as you can. But uh these sets are somehow constraints of of how much you can take from a certain collection of goods in total. And so uh across all all the sets um where some element occurs uh you can't exhaust in any of the sets the capacity.

8:15 You could you could say that's a somewhat natural problem. Uh I think if you first if you just stare at set cover and think about what would be the natural dual problem it's very hard to come up with uh the right definition that's both intuitive and correct. Uh but if you do do the mechanical dualization often in hindsight it's much easier to make um make sense of this problem or rewrite the problem slightly so that it becomes uh somewhat more intuitive.

8:50 Okay. So, um the dual set cover uh problem looks like this. The constraints are essentially um summing summing these amounts of each universe elements over a set up to some capacity over cost. How can we use this uh in making a an approximation algorithm? uh what we'll do is is actually not a new algorithm but it's the same we've seen before the greedy set cover algorithm and if you remember from last week or so um the analysis there was this price lema where we uh we said so the algorithm again just um to remind you or make that clear again we always pick as the next set greedily the one that gives us per element that we cover now with this set that we didn't cover before. So per new element, the least cost. Uh that's the most cost effective set and that's the one that we pick and we do that greedily. And back then we showed that there's uh each element is covered at a certain price. Namely, when it's first covered, we compute uh what's this price of the set we included per new element and fix that. And uh we showed that this price can be upperbounded because you could have at any point in time just taken the optimal solution to cover all that's left.

10:15 Uh here we'll see a slightly more fine grain analysis if you want although the result is the same. Um what we'll show here first is that if you take as dual variables the price at which this element is covered but you have to scale it down. Remember dual fitting always has a has to scale down to bridge the duality gap. Uh we scale down by hn the harmonic number again. Then that's a dually feasible um set of set of values for the dual variables. Um so intuitively you should think of the price as the dual variable but we can't exactly use that because uh it's it wouldn't be feasible. Um so uh why is the scaling down good enough? Um if you remember the dual constraint let me just copy this uh that we don't have to remember.

11:40 The dual constraints are are these only take as much from the good up to the capacity. Um and I will consider some specific set. We'll have to show that this satisfies all the constraints. So let's pick an arbitrary one. And if we show that that's satisfied, that's good enough. And let's say L is the number of elements in this set. So that sum as L terms uh like at the time when we analyzed this algorithm the first time around let's name the elements in the order they are covered by the algorithm. So whenever you include a new set the elements that you now for the first time cover they become the next elements in this sequence. And uh at the time when when we cover the element ei total, we don't know how many uh elements from the set SJ we've already covered, but certainly at most I minus one because we've covered I minus one in total. So there must be L minus IUS one uncovered elements left. If you scroll back or go back in memory for to last week, this is a very analogous to what we did back then, but we applied it to the entire set of elements, not restricted to one uh set.

12:54 All right. Uh so of course that means if we take this SJ now and we do because that's by assumption where this EI is covered or we could have taken that SJ now uh we would cover the element EI and essentially the others in SJ at the cost of E of of SJ divided by at least that many fresh elements. And so we don't know if we eventually took set SJ, but the price that we paid for EI can't have been can't have been higher because at least we could have picked SJ. Okay. And the actual set that we choose here, this SIAR is only better.

13:42 Now, if you uh remember what that means for our variables, that's just the scale down. So same same thing I divide it by harmonic number.

13:53 Um and now again uh look at the dual constraints. So we're continuing them from there. We take the sum of the y in a specific set and I'm going to rewrite that to have indices in the order at which the elements are covered. So we assume here that sj is consists of the elements e i1 up to e i l.

14:21 Uh there's some ordering of the elements or some there's some indices of the elements in this ordering. So that always works that always exists. So we can rewrite the sum as uh going from through these indices m from one to l. And now we insert what we know about these variables, namely this part.

14:59 That's what we use. Now, see, I'm trying to be very low on memory load today. Uh and then you notice this um this denominator is is essentially just summing um summing up the first m the reciprocals of the first m integer. So that's another harmonic number and this comes from just going through the elements in the set here always makes this uh one larger. So we have to reverse the summation but that's essentially the same as as we've done back then in units unit 10. Um and so uh ignore that things are reappearing below there. That's another harmonic number the elf one and l is at most n right l is the size of a set. So it can't be more than the entire universe. So this is below one. So we get our upper bound by the cost of the set and that was the dual constraint. Okay. So this this is all that's why there's the end of the proof.

16:05 And the sneak peek here you already had is if you do this uh for for all if you show this for all the constraints that means our scaled down y And then with the chain of arguments at the beginning, the the dual fitting in general copying is so much fun and it doesn't cost uh you derive this part. So we're using that chain of argument and our delta is hn. So we get an agent approximation. Now you may say amazing we've already known that. Uh but in a way the algorithm uh the analysis of the algorithm back then needed a bit of a a magic insight that you consider this price of an element and that you somehow upper bound this. It was much more ad hoc and uh coming out of thin air. Whereas here the dual the dual constraints very very much guide you to do the right thing. So it's it's maybe a bit less surprising or bit easier to come up with the with the analysis in this case.

17:36 Uh a small extra benefit uh but I'm not claiming this is unique to this analysis technique is that uh you see you could actually have taken HL as the scaling down. If you take the largest of the sets because we're for each of the constraints we only needed HL L divided HN to be at most one. That's also true if you pick instead of N the largest of all the sets cardalities. There's a slight bit better. Of course, in the worst case, not that much. But set cover becomes kind of boring if there's a set that covers most of the elements. At least uh it's often clear whether that set should be part of the solution or not. So maybe this is um there's some beyond worst case analysis that one could do there.

18:25 Another thing we can get from our duality theory here is is another um another piece in towards towards the another piece of evidence supporting the claim or supporting the suspicion we might have that we can't do much better for set cover. that this harmonic number is essentially the best worst case approximation ratio we should expect if we don't look at any other instance specific parameters and uh so if you raise that uh our our approximation algorithms can be seen as relying on the integer linear program and its relaxation. So we've shown with the previous algorithm essentially that the integrality gap is at most hn because we bounded um the cost in terms of the the optimal um LP value and I mean this is maybe I should show that here again right this is uh the bound we get in terms of the set cover we compute is hn times the optimal objective value for the for LP and that of course is a bound for the optimal um integer linear program. But we really get a slightly stronger result here if you want or a slightly um more insightful one. So we've we've really shown that the integrality gap is at most hn. And u maybe we can also show that it's at least hn. So that's the integrality gap is a a key barrier as long as you rely on on algorithms that somehow use use ILPS LPS in a in all the ways we've we've seen they uh there won't be a way to improve um and that's indeed the case or at least almost um there's an example that we'll construct that shows that this integrality gap is at least a constant factor times hn And the precise thing we'll show is this uh and it's exactly as you might want to read it. We will show the optimum cost of a set cover instance in the example we construct is is log of n + one whereas the fractional optimal is essentially constant.

20:53 And so I think that example that that worst that bad example or bad family of bad examples is kind of insightful in its own right. It's a clever use of linear algebra. So here it goes. Uh we can build this for an arbitrary arbitrarily large input size but it has to be a power of 2 minus one. So there's some L and uh we can essentially use numbers of L bits including uh the leading zeros but we don't include zero. So that's important. Uh the universe as before by the way uh is is one up to 2 to the L excluding the last one. So up to 2 to the L minus one. We'll treat these numbers. Well, so I'll I'll write the bold base I if I mean the vector we can treat these numbers as a vector which just consists of the binary digits. So if I have the number I don't know uh what's a what's a good example maybe nine.

21:53 Uh I can write this as um as 0 1 0. Oh, that's actually not a nice example because it's symmetric. How about we make it 11? Two more.

22:14 So, you can write 11 in binary. Uh, and then I'll do the the bold base 11. That means just the vector where you take the entries in order. the order is actually not not relevant for what follows. Okay. But we'll we'll identify the numbers and their vectors in the following. So the sets that we'll define SJ or the same essentially same as the universe uh I I don't think the zero should be there. I think should be one up to n minus one. um is exactly all the vectors I or all the numbers I such that the vectors have uh a scalar product that is one modulo 2. All the vectors are binary there only zero ones. So all the scalar products will be integral and if you take modulo 2 you're just asking is this odd or even right? Uh there's a maybe a strange definition but you'll see in the proof why it's useful. the cost for all the sets will be identical. So the whole thing has a lot of symmetry which is um on purpose.

23:30 Uh the size of each of these sets is exactly n + 1/2 or maybe nicer would be to write 2 to the l uh so 2 to the l minus one. Um and that's also the number of sets that a specific number occurs in. And to see why that's the case, if you take any any number J and look at its its vector, um it might be some arbitrary um collection of zeros and ones. The all the only thing we know in general is that it is not the all zero vector. That's why it was important to exclude the zero here. So there's some one and maybe I'm looking at the last one. Doesn't matter where it is. I can take I to be an arbitrary pattern on the first on on all the positions except for this last one. And I can always put the last digit so that the uh itj is one. I can always fix this. Uh say I'm I'm doing zero one zero one.

24:42 Just making this up arbitrarily. That's fixed. And now there's this this position that I I cannot fix. Uh for this one I have to calculate. And so you see uh they have a one in common on the second position. This zeros out everything else. So all that's left of this excluding the red part is a one, right? Is one.

25:09 All the others are zeros. So I have to put the red to zero to make that a one. If I had put a one here, it would be the scalar product would be two, which is 0 modulo 2. So it's a a simple proof that um no matter what J looks like, as long as it's not the all zero vector, you can pick all but one bit arbitrarily and you can always fix it. actually in both ways the red position decides whether it's part of SJ or it's not part of SJ and there's perfect symmetry because these uh sets the way they're defined with I and J I and J are you can you can swap them around that's why if the size of a set is a certain quantity the number of elements the number of sets an element occurs in is the same quantity Okay. Uh so that's that's curious enough. Uh now this is enough to show that we have a very cheap fractional solution because you can just pick a two out of n plus one fraction of all the sets. Uh they in total will be a set cover because of this right. Uh the dual constraints were uh sorry the primal constraints is what we need.

26:43 is for every element you want that the the sets that are uh containing this element in total provide at least one and that's satisfied if you have that many sets and you set each to the uh reciprocal and so the optimal objective value will just be n times for um covering all the elements Um so is the number of sets should be number of sets right uh why is this n times I think this should be the number of sets because we're just summing up all the variables so it's even slightly better you get an um is the number of sets in total oh the number of sets in total is is n is n. Uh so yeah okay sorry I was correct it's the number of sets but that is n I confused myself with the size of the sets but really number of sets is for all those um all those j uh I think I'm I'm I confused myself here with the indices this should be from one to n But there's n of them. So we have n times the uh the the cost times the variable and that's roughly two plus minus at the same time. Um how many sets do we need in any actual set cover integral set cover? That's a bit tricky to uh to to properly prove. It's it's kind of clear that um the sets are really big. So in principle they could be two that just perfectly overlap. The first covers the first half, the second covers the second half, then we'd be done. Uh but the way they are chosen with these bit patterns, maybe you get the feeling that this is unlikely, but there's a nice formal proof.

28:53 uh suppose um that there was a a set cover that contains only k strictly less than l sets of say uh I mean all the sets contain correspond to some numbers so say these are the numbers i1 up to i k I'm going to write these as row vectors in a matrix so that's a a k * l matrix then it has uh k rows for the k numbers and the columns are the digits because it's a K* L matrix. It cannot possibly have rank L. It has to have rank at most K. There's not much you can do about it. And so if you uh look at the the null space, so set of all vectors that if you multiply them to a um you get you get zero. Then that's not just the all zero vector. You get some other vector J. So that uh the product is z is is zero modulo two right this is where the whole thing is um also the rank if you want we're we're computing in the field f2 um now that means that j if you look at what this matrix product is doing matrix vector product it multiplies vector j with each of these i's and takes the scalar product and the outcome is supposed to be zero.

30:22 That means for each of those uh i1 up to ik j is not part of the set because they were defined to exactly be the ones where this uh scalar product is one and so j is not covered. Okay. So that means uh you have to include at least l sets. I guess l is also sufficient but we don't care. um at least the optimum is log n + one namely l and so if you take the ratio of of log n and two you get slight slightly better this is log base 2 we wanted log base n log base e but then you get this result so as long as we're doing essentially um integer uh linear programming based tricks we won't expect something better than this this uh harmonic number approximation ratio ratio for set cover.