Video 11-2: LP Rounding

0:02 Now over to the new thing. In this section, we'll look at the first way to use LPS, namely by uh rounding these fractional solutions. Uh but let me take a step back before we get to that. Uh we usually think of um hard optimization problems in this chapter. And it turns out that these integer linear programs, they're nplete.

0:24 So you can embed every possible NP problem somehow as an ILP. So in a in a way if we uh find good techniques to work on ILPS that's going to solve all problems. Uh but yeah usually we're have to work a bit problem specific but we'll we'll keep that in mind that it's potentially very powerful. The hard bit in approximation algorithms or in the design of approximation algorithm often is that you don't know how good the optimal solution is. And so having some way to bound the optimal solution. It cannot be better than some value is super helpful. And there's an easy way to get that using the uh connection between ILPS and the LP relaxation. So the LP relaxation I think I didn't didn't have on the slides for the repetition is just you take an ILP and you drop the integrality constraints you replace them with just greater equal zero.

1:24 So um the general approach could be you formulate your problem as an integer linear program knowing that you're not going to solve this op optimally in polomial time then you just drop the integrality constraints turn it into an LP and you solve that one optimally which we can do in poly time. So you get some optimal solution for this fractional one. And the cost that you get for the LP is going to bound the optimum cost of the original IP ILP because you're only making the feasibility region bigger. You're allowing more solutions for X. So the cost cannot get worse.

2:04 Now that's almost a cool algorithm except that somehow we can't get a solution for the original problem in the general case like it is not obvious uh if there's a general approach for that we somehow want to go back to a solution that's feasible for the original problem and not just the relaxed LP right okay uh but what what what could we do a simple version is is it's non-integral numbers let's just round them. And of course, this is easier than it sounds because you by arbitrarily rounding you're not usually going to get a feasible solution. Uh but sometimes you can even even if you can uh what will come up again uh what we discussed back then is this notion of an integrality gap which is the difference or the ratio I should say between the optimal objective value of the uh the LP and the ILP. uh that's going to be a barrier for how good this approach in total can be because you're uh you're trying to get some some solution for the fractional one to get it back to the ILP. So it's you have to do something there. Uh I guess it's not it's not clear if you can if you necessarily have to have an approximation ratio that's the integrality gap. Maybe you can do something smarter.

3:30 All right, let's see this um in concrete terms and we'll return to our uh our favorite set cover problem. Again, uh remember this is we have a a ground set and we have sets SJ that we want to pick some subset from. We have these uh sod dashed mode. The input was S which is a collection of K subsets of this universe. We want to pick a subset of this collection of sets so that we have every element in the universe covered. So by one of the sets and they have certain costs. So the uh goal is to minimize the cost as an integer linear program. We can write this as XJ a variable that is one if the uh element if this set SJ is part of the solution and zero otherwise then this is going to get us the total cost of the cover we're picking. How do we enforce that it is a set cover for every element of the universe? We sum over all the sets where this element is contained.

4:39 That's this notation here which we'll use a bunch in this chapter. So kind of memorize that one. V of E is the indices. So all the sets where E occurs. We sum over all those and we require that at least one is one. That's what the sum does. If you restrict your numbers to integers.

5:02 Uh first of all to have it in normal form I wrote X is an integer or a natural number. But you can easily work out it never never helps to make any of the uh entries of x bigger than one. So an optimal solution will always be in 01 to the k. That's the ILP and uh you can relax that to a linear program if you just drop the integrality constraints and make it an x greater equal zero and for that we can get a solution in polomial time and um that's true in general. Um if we write the optimal objective value for for the two problems with a subscript of the problem name then the optimal value for the integral problem um it's the other way around right we're minimizing so this is only going to be better than the integral uh problem. So we get a lower bound on the optimal solution.

6:14 How do we make use of that? Uh one option is to just round so conservatively that we're going to guarantee the solution is a is a feasible solution for the integral for the integer linear program. And one way to do that is to take this frequency of uh any of the elements. So what's the the largest number of sets that any element occurs in? That's what we called frequency. Then we take our optimal LP solution, some fractional solution, and we're going to pick all the sets where the variable is at least 1 / f. That's what I mean by round conservatively. We're rounding up way further, way earlier than we would normally think of rounding 0.5 up and everything else below rounding down. Uh here we're rounding up potentially much earlier if f is larger than two. And so all of these we return and that's our our answer. Let's see how well this does. Uh you can show it's an f approximation. We've seen that before, but still uh it's it's an entirely different algorithm. So I think it's um it's kind of reassuring that we find the same same approximation ratio.

7:39 And remember set cover generalizes vertex cover. So here I could even have written weighted vertex cover where the vertices have some uh some weight not just um counting the number of vertices. uh and there's a two approximation because in vertex cover every edge occurs in exactly two neighborhoods or two incidence lists. Uh let's prove this quickly. Um we have two things to prove. First of all that the algorithm even computes a valid set cover and the second the approximation ratio. Now to see that it's a set cover take an arbitrary element from the universe. We have to show that it's covered in the solution. Now we know that this Xstar the optimal solution was feasible in the LP. So in case you forgot uh that's the LP, right? It's worth taking a picture.

8:55 So it has to satisfy in particular this constraint for this specific uh e. So we have the empty sum is greater equal one. Uh you're summing the the values of these sets. Now again it's a fractional solution. So these could be uh any number well between zero and one. You're never going to get larger numbers in an optimal solution. Uh okay now we know that every element occurs well in exactly FE uh sets that's how we defined it but in at most F for the global frequency. So one of these if if that's going to be true for your XJ star, one of those XJ star has to be bigger than one over F because they're all non- negative, right? Suppose they were all smaller, then you immediately get a violation of this. And so one of those at least is uh is part of our output and so E is covered. We could have several right in the we could all of them could could have value one over F and then recover E many times. That's okay.

10:08 How about the cost? So uh we have to show that whatever the algorithm here outputs is an F approximation. Now we're using so far this this was only using the feasibility of XAR. Now we're using that it's an optimal solution of the LP which means we have this uh ctx the optimal solution of of the LP problem and that's a lower bound on the optimal solution for the for the integral problem and for all the sets that we picked we have this lower bound on the xj entry 1 / f otherwise we wouldn't have picked that set so But we can use that to just uh bound the cost. We take the cost of our set that we pick. It's the sum of all the uh sets that uh solution and it's it's a an F approximation because you can rewrite the cost of the solution. We compute using what we know from the rounding as f times this this sum.

11:16 And uh that here you can upper bound by taking the value on all the sets not just the one you picked and that's essentially the optimal uh objective value of the fractional of the fractional problem or the the LP problem. And we know that that's a lower bound on the one for the integral. So here we're just using this this uh key fact here. And so we get what we want it. the cost for the set we pick is at most f times the optimal solution.

11:52 So there's another way to get the same kind of approximation guarantee we've seen before. Uh just as a quick argument this is also in a way best possible. you can't uh in the worst case show something stronger and um an insightful instance to look at I guess not even for this for this for this algorithm is the the fully symmetric instance uh suppose we're we have some some numbers f and n so f is a divisor of n and otherwise um uh they're arbitrary then you have the universe of these n elements and you pick these specific uh sets and you n sets as well. So same number of elements and sets uh and every set uh is just kind of you shift around a a circle. You take a certain fragment and then the next element takes one more element and so you shift that along and by controlling the size you can control in how many sets each element is contained.

12:57 Um the cost can be set to one for all all the sets. That's fine. If you solve the LP for this very symmetric instance, one optimal solution is where you get 1 / f for all the sets. And uh then the algorithm we've just discussed just outputs the entire collection of sets. Whereas clearly you could have covered this uh the cycle by taking n divided f sets. So you're an a factor f away from optimum and uh there's not much you can do about this in that general sense.