Video 10-6: Approximation Schemes, Knapsack

0:05 In the next section, we'll look at some uh even more ambitious approximation algorithms where you can wish for a specific approximation guarantee up front. These are called approximation schemes.

0:19 And um indeed for the problems that we've seen so far, these are unlikely to exist. Um both for vertex cover and for set cover. Um as a generalization um we've seen that uh there are certain barriers below which uh so certain approximation factor like two for vertex cover where it seems unlikely that we can find an poly time algorithm that beats this approximation factor.

0:46 Uh for other problems um maybe we uh can hope for something better and the appropriate definition is is this one. There's there's two versions of this pest FP test. Uh you'll see the difference um in the running time in a second. So the setup is we have an we have an optimization problem and here I picked a minimization problem for uh god knows why uh it doesn't matter. Um so here we minimize things then approximation ratios will be above one right because the solution we get is worse than optimum. So it's going to have larger cost than the optimum cost. Uh and an algorithm now is uh a polomial time approximation scheme or pest. Uh if it if it takes two inputs um a number epsilon small small rational number and a specific instance and we usually write this um with epsilon in the subscript because you can treat kind of curing epsilon in and leaving x. uh so you get an algorithm where you just specify epsilon.

1:55 So for a pest this a epsilon has to be a 1 plus epsilon approximation algorithm for you and it should be poly time but you treat epsilon as fixed. So the running time has to be polomially bounded by the length of the input as usual but epsilon is treated as a constant. And so you could in principle have a running time like this or I guess even like yeah it looks like an FPT time but nobody forbids us to have something like uh one over epsilon in the exponent of n or something even crazier than this like is you treat epsilon like a constant. I think this should be xp running type um if we want to make the connection precise.

2:50 So you can get an arbitrarily good approximation. But if you view it as a function of epsilon the uh behavior the growth with when epsilon goes to zero the growth could be arbitrarily bad.

3:05 And so well whatever that means right it depends on the actual functions. Um the stronger notion is an FP test a fully polomial approximation scheme. Um it's the same setup but now the running time has to be a polomial in both the input size and one over epsilon.

3:26 So if if here you uh view the function um view the function that maps epsilon to the running time I guess I I can write this as time a epsilon of n.

3:49 Uh then uh and now we have another parameter in again for some for some specific constant. Does that make sense? Well, this this function in the P test case is unbounded arbitrary and for FP test is polomial.

4:25 But formally you should you should uh go by this definition. The running time is a polomial in in the input size and one over epsilon.

4:34 Certainly fp test is a much stronger notion. Maybe it's too strong. Right? Uh does this even exist for any hard problem? Uh we wouldn't study it if it wasn't the case. It exists for some problems, but we'll see. It's only a a selected um class of uh really lucky problems that will have an FP test.

4:58 Uh one example is the NAPSAC problem. A good old friend from unit 3 when we talked about uh pseudo polomial algorithms. So because it's a couple of weeks ago, let me remind you about the the problem and the notation. Uh so the 01 knapsack problem means we can we only have items that we can either take or not take. The items are just numbered 1 through n and they have certain weights w1 to wn and they have values v1 to vn and uh we have a knapsack of a certain capacity b which is the weight capacity. I can stuff in items of total weight at most B. And my goal is to maximize the value. So these could be separate in principle. And how could we get an approximation for napsac? What we care about at the end is the value. So we might try to round the values. And by making them uh more coarse granular maybe we can reduce the size of numbers that are involved. And that's how it how it will tie back to the pseudo polomial algorithms we've seen before. Uh there's a slight um a slight nitpick or a slight uh twist um if you want that we have to get around first.

6:22 Um, as you all will remember readily in unit 3, we solved the NAPSAC problem with a dynamic program uh that has has this table um where uh we have entries for a prefix of the items. So we're only allowed to use items one up to n prime. And um we're restricting the weights potentially further than b. So specifically this this V nprime B prime was this largest value we can get or a selection of items among the first np prime ones where total weight is at most B prime and then we could get a a recursive description of this. uh we could fill this um and essentially the running time is is dominated by the size of the table which is n * b just the number of combinations for these uh indices in the table the total time because you have to compute with numbers compute with values you essentially get a logarithmic dependency on the size of these integers because you have to add them up um but even so here the logarithm of max int uh log of max int is always going to be less than the input size right because you have to write down the numbers. So uh it's it's the correct way to say it but uh in terms of the pseudo polomial algorithms where this maxin came from the real culprit is the b here because b is a number that we have as part of the input and that could be exponential in the input size encoding.

8:06 So this solution from back then was great if the weights are small but now we're trying to round the values and leave the weights unchanged. So it's a little inconvenient. Uh luckily you can take the same core idea of a dynamic program and tweak it so that the size of the table depends on the values and not on the total capacity of the knapsack. It's slightly less efficient in general and is slightly more inconvenient. That's why I didn't present it that way in unit three, but you can do it. Um, I'll make the assumption here that all the weights and values are natural numbers. If not, you can scale them with the they're assumed to be rational numbers. So, you can scale them with the common denominator.

8:56 Um, that might blow up the numbers. So it's it's not necessarily without loss of generality but it's an assumption that we use for getting this approximation algorithm here. So this is kind of important and we define a different dynamic programming table as follows. We take the smallest weight that we can get again from items of a prefix. uh but now we restrict the value instead. We want value exactly v it's a bit awkward maybe from just solving the problem but it works uh in particular you can write a recurrence for this. So the the minimal weight I can get to pick items from this set to have value exactly v I can uh if my next item that I'm the last item I'm I'm considering here compared to n prime minus one if that one has value less than v then I can try to include it that's this solution. So I'm I'm including the weight of this new item and then for from the previous items I want to pick value exactly V minus the value of this new item and otherwise I'm I'm not picking this last item. So I have the same solution as I had previously.

10:19 Uh if my uh new item is too valuable then I can't take it. It's a bit well that's by definition. It's not so intuitive. Uh the final solution here is more complicated, right? The you have to go um you have to go through uh starting at the at the largest value, you have to go through all the entries and check what's the largest V where you get an entry that's less than B. Uh but you can do it and you can fill it recursively like this. Um there's some initial values left because we have this restriction equal v. there will be many entries that are essentially left at zero uh or left at a plus infinity because we can't exactly get value anyway.

11:08 But that's not a problem. So that's a nice exercise in in dynamic programming. But the point here is uh that we can get a solution an exact solution for the 01 knapsack problem with um a total time like this that comes from the number of entries. We have n for this and how large do we have to pick the values? Well, at most n times the largest value for any item. And uh so that gives you that time. It's the the size of the table. And then again computing with numbers takes logarithmic uh bit complexity.

11:53 And with that we can build an FP test as follows. Um we make a a convenience assumption here that uh we only consider items that fit in the napsack by themselves. If they don't, you just remove them, right? They're never going to be useful. Um this is just something again that pops up in the proof makes makes arguments cleaner. Uh the algorithm then is conceptually round the values and call the dynamic programming algorithm because the dynamic programming algorithm is in the running time and space very sensitive to the maximal value of any item. That's going to be uh um reducing the running time. And what we'll have to show is how good this is. But uh what do we mean by rounding? Specifically, we uh take K to be um essentially the largest value and then um multiplied by epsilon / n and epsilon is the parameter that we want as a approximation guarantee in the end. So the output is supposed to be a 1 plus epsilon approximation.

13:02 That's the goal. So we pick um uh a granularity k defined like this and we um round all the values to multiples of k or well we could I could have included the k here but uh we're just yeah uh rounding them in units k we express all the values with uh units unit Okay.

13:34 Uh okay. Uh to show that this is indeed um an FP test, uh let's briefly look at the running time. You look at this code that's not doing much. So the running time will come from this dynamic program. And uh you can you could just plug in what we know here. Um let's define this uh capital V tilda again as the maximum of the vi tilda. So the v tilda is the rounded v right. So this one is the rounded maximal v. Uh that guy we can bound by the input size as I mentioned before. It's the log max int. And then we insert what we know for v just by definition. um it's going to be the largest V divided by K. The rounding uh we just ignore upper bounded by that and then we insert what we know about k and k will uh give us another factor n here up here it will cancel with the v and we get a 1 / epsilon and that indeed is a polomial in the input size the size of the encoding of the input and one over epsilon.

14:56 So the running time is fine. It's going to go up with epsilon and the space is going to go up with epsilon but only polomially. So uh good enough for an FP test and um probably the best you can ever hope for. We still have to show that this is um an approximation. So uh yeah what I said earlier I guess here is a maximization problem.

15:32 So we want to show that the uh value of the selection we get from this algorithm is not too far away from what the optimum gets precisely a one minus epsilon factor at most.

15:46 And that that's again a relatively simple argument but a a cute little little trick um to calculate. We start with an optimal solution for the original problem um by definition. So this the value I'm just going to write V of a of a set of items to mean the sum of the values and that's the optimal value by definition. Um, and now if you go, let me maybe copy the algorithm just that we have this on the side.

16:31 Uh, for this um, see why this is true, you just have to insert what the V tilda is. Um if we multiply v tilda by k then I'm basically scaling up with this k again and then I'm have what's written here is k times this rounding down I can upper bound that by vi um by the way this uh this notation here is kind of vector vectorzed uh like like numpy or or matt ml ml madlap uh where this is this is a vector v and you're applying this operation to the entire vector element wise. So we're doing it for each bi. The upper bound is is obvious from this and the lower bound is kind of also obvious. Uh all you're using is that x rounded down is less or equal x and at least x - one. Okay.

17:33 Now um we use that the DP napsac returns the optimal solution but for the rounded values. So what we output will be um at least as good as the optimal solution if we substitute the the rounded values, right? Uh because it's optimal for this for this instance and also um opt whatever it is will be at least as big as the most valuable items because we assume that they all fit in the NAPSAC. And with that preparation, we can easily puzzle the result together. The value of our selection is the sum of all these values that we pick. Now, we're using this um inequality from from the way here inwards. It's K times the rounded values at at most at least K times the rounded values. Then we're using that inequality to get from our solution to the optimal. That's this one. Now I'm using this again but in the second direction. So this is uh at most on the unrounded values on the same instance minus a small correction because I'm I'm uh ignoring the rounding.

18:52 That's exactly the optimal value. And here I'm inserting the definition of K. Again, if you already forgot, here it is. And that's epsilon * v. And so now with this last equation, this v is at uh at most opt. So we get our desired bound.

19:16 Um in a way, uh conceptually this is I think easier than the the exact analysis, um makes it seem. If you have a a pseudo polomial algorithm where you essentially pay this this non-polomial part in the running time for certain numbers, rounding the numbers to something more uh uh less precise is going to improve the running time and you can often puzzle this together to um uh an approximation scheme that way.

19:50 Um because we're out of time, I'm not going to prove this part. I'm just going to make the statement. It's it's a the proof is not is not hard. Um is a kind of almost an exercise level problem, but I think the connection is is really nice to make. Uh you can say having an FP tests the problem a lot or you can say there's deep connections to previous areas we looked at. If a problem has an FP test, so I'm I'm using the complexity theory class notation here, but uh this just means U has an FP test. Then the uh canonical parameterization of this optimization problem FPT world uh is is back then that has an FPT algorithm. So um for certain problems this already rules out that we have an FP test just because we know the problem is is W1 hard at least it makes it very unlikely to have an FP test.

20:48 Um and the second statement is is a bit of the uh the other direction of what we've just used. If we have an FP test and also the cost of any specific fe um feasible solution is bounded by a polomial of the maximum value. So this is not a strict like this is a potentially exponential in the input size and then you take a polomial of that thing that's not a strong restriction but uh you need it for technical reasons. Basically if you have an FP test you can construct a pseudo polomial algorithm out of it most of the times and so it shows that these two uh notions are really deeply connected um fpas in the sense of rounding and pseudo polomial in the sense of analyzing the running time dependency on on how big numbers are they're uh with a little bit of uh closing eyes the same