Harvard University · 1:25:41 · https://www.youtube.com/watch?v=vnS9_NKoEKI
0:00 So today I want to finish the um finish the analysis of the dual fitting analysis of the greedy algorithm for set cover or weighted set cover. um and uh I'll do one I'll I'll do one other very simple example for dual fitting uh namely unweighted vertex cover and you're going to So the the next homework is going to be out tonight and you'll you'll see a problem related to that. um to to vertex cover.
0:31 Then I want to talk a little bit about uh a limit a limitation of of this whole uh LP framework for approximation algorithms, okay? So I'm going to introduce something called the integrality gap of an LP relaxation. And then I'm going to talk about
0:46 uh more approximation algorithms, namely polynomial time approximation schemes and that's where we don't just want say a two or log n approximation, but we want a one plus epsilon approximation uh where epsilon is given in the beginning, okay? Uh so how do we get for any fixed epsilon a polynomial polynomial time approximation? Sometimes that's not possible but we'll see an example where that is possible.
1:14 Okay, so last time I defined the set cover problem or the weighted set cover problem. Uh there are m sets, each one is a subset of the universe. The universe for us is one up to n. And a set S has a cost CS. And the goal given this in this an input, the goal is to find a sub collection of the input sets which covers the entire universe, okay?
1:39 You must cover the universe and you want to do it as cheaply as possible, minimize the sum of costs, okay? The sum of costs of sets you take. So the greedy algorithm well in the unweighted case if you know, I think people have seen if you've taken CS 124 you've seen the the greedy algorithm um for the unweighted case is you just keep taking the set that covers the most new elements.
2:00 Okay? But when you have costs on the sets, then, uh, you just slightly alter that. You pick You pick the set, as long as there's an uncovered element, you pick the set which minimizes the ratio between its cost and the number of new elements you get to cover by picking it. Okay? And theorem um greedy is a log n approximation.
2:33 We'll We'll even see it gets something slightly better. Um, just some history, I guess. Uh In the unweighted case, when you when all the costs are one, that's what I mean by unweighted, this greedy algorithm is due to Johnson, uh, back in '74, I think.
2:56 Who's writing today? Okay, great. Uh, and also, I believe independently, at least they didn't cite each other, um in discrete math, '75. And in the weighted case, I don't know how to pronounce this name. And that was in '79, um Okay, so um, we're going to take a primal dual look at this, uh, at analyzing this algorithm.
3:44 Okay? So, if you took CS 124, we did analyze it there. We didn't talk about primal dual, but um You can take You you look take a primal dual look and for one of the homework problems that I'm going to release soon for vertex cover it's going to be for weighted vertex cover. Um
4:03 even it's not just an issue of the analysis, even to come up with the algorithm I think it helps you to have a primal dual look at the problem. Okay. Okay, so so the LP relaxation for set cover, I said last time
4:23 in the primal we want to minimize the sum over S of CS times XS where XS is one if you take the set, zero otherwise subject to uh for all I from one to N you need that the sum over sets containing I of XS is at least one and that for all S XS is at least zero. Yeah.
4:49 So when you say the LP relaxation, does that mean there's a unique No, that's a very good point. Yeah, um I shouldn't have said the LP relaxation. So uh an LP relaxation. Okay, so if you So the set cover problem is actually this problem but where you have that you have the constraint that XS is either in zero or is either zero or one. And we relax that to just put a linear inequality. But you could imagine formulating it um another way and getting another LP relaxation of another formulation of the same problem.
5:26 And you know, maybe maybe using that LP relaxation would give you better results. So there's actually I'm not going to get into it in this class but there's actually a a formal way of doing this. So given given some like integer programming optimization problem where you have like integer constraints
5:45 um there's a systematic way of converting the LP of of um getting more and more refined LP relaxations which get which become better and better approximations to the integer constraints. Um so if you want to read more about this, you Google for like the Sherali-Adams hierarchy. Okay, so I'm not going to talk about that in class.
6:08 But um there is and you can show that uh eventually this thing becomes the integer program after But then by that time you've blown up the LP to exponential size, so Okay. So that's the primal. And the dual
6:31 is we want to maximize the sum of e going from 1 to n of y sub e subject to the constraint that uh for all sets S the sum of elements in that set of y e is at most c s and also y is a non-negative uh vector.
7:00 Okay. So we'll do dual fitting. I think I mentioned this at the end of last time, but now I'm actually going to prove something. So dual fitting. We'll show how to maintain dual solution as we build the primal. Okay.
7:37 So when we take a set S. Okay, we're going to set X sub S to 1 in the primal and two for each newly covered element E uh we'll set Y sub E to equal C sub S over uh the number of elements newly covered by S.
8:32 Okay? So, this is this is what we're going to do. Remember the usual thing, we know by weak duality that the uh that any primal if we have two feasible solutions, one for the primal, one for the dual, we know the primal cost is at least the dual cost, right?
8:52 Where opt is sandwiched in between. Um so but they have to be feasible. So, as it turns out, this Y might not be feasible, but we'll show that if you entry-wise just scale down by log n, it will become feasible. Okay?
9:09 So, ahem let me let me write down some observations. First of all, the cost in the primal of X is the cost in the dual of Y. Okay, we've rigged it that way. And we'll show that in fact, we'll show why over the Kth harmonic over the Nth harmonic number is feasible for the dual.
9:48 And that's going to imply a log n approximation. And definitely I should also say I mean I didn't say it. The primal will be feasible, right? The primal is feasible. Because we keep doing that while loop as long as there's a constraint that's violated. Okay, so so now we just need to show this.
10:25 So claim y over HK is feasible for the dual. So proof. So the I mean this constraint's never violated. The the only trouble is this one. So we need to we need to show that for all sets S this summation is at most CS times log n.
10:55 Need to show that for all S the sum of e in S of y e is at most CS times log n or actually we'll time HN. HN, what's K? There's no K here. Okay. So let's order the elements of S by uh uh by when they're first covered.
11:41 So, E1, E2, EK. Right? So, let's say S has size K. Okay. So, let's look at right before right before EI was covered. So, what I want to say now, what I'm going to write af- you know, in the when I finish the sentence,
12:22 I want to I want to basically say that, you know, each one of these EIs at some point when it's first covered, it's going to get its Y to be set, right? Now, what E might not get EI might not get covered by S. It might get covered by someone else. Okay?
12:40 But, I want to argue that when EI was covered, I want to argue that the price that we set to YE could not have been that high. I want an upper bound on that price. I'm calling My Y is for me the price vector. Okay?
12:55 So, what's some bound? Can anyone tell me a bound on the price of of uh that we that we will assign to YE? So, right before we right before we covered EI, right? So, EI is not covered, meaning we haven't chosen S yet cuz S would have covered it. What would be the prices derived from choosing S at this point.
13:34 CS over what? And And what's a what's a lower bound on Yeah, K minus I. K minus I plus one, actually. Right? Right before EI was covered, we could have chosen S at price CS over K minus I plus one. Okay?
14:06 So, we know that implies that the price of EI is at most CS over K minus I plus one, right? That's what greedy does. It chooses the thing that gives us the lowest price. Oops, I just lost one.
14:28 So, this implies that this summation this summation right here that star is at most C sub S times the sum I from one to K of one over I, which is exactly C sub S times HK. Okay? And K is the size of S.
14:56 Remember, K here is the size of S, which is certainly at most N. In fact, we proved something stronger. We proved that uh if all the sets in your in your set system have size at most K, then actually greedy gives you a log K approximation. Okay?
15:16 So, that's it. I'll do just one more, even shorter one. So, one more. Vertex cover. So, right the input is an undirected graph G equals VE. Okay. Uh I'll say this has size N and that has size M.
16:20 And the goal is to pick as few pick um pick a subset of the vertices as small as possible such that each edge in E is incident upon at least one vertex of S. Okay. So, there's a greedy algorithm for this problem which we said in 124, but I'll I'll write it again.
17:09 So, greedy algorithm. While And by the way, notice that um um Notice that vertex cover is actually a special case of set cover. Right? Do you all agree with me? So, someone tell me why. The edges are So, okay, so in vert- in set cover, there's a universe and there is a collection of sets. So, what's the universe and what's the collection of sets?
17:52 Right. Yeah, so the every vertex is a set and every edge is an element of the universe. That's right. Yeah. Okay, good. So, greedy, while there exists an uncovered uh while there exists an uncovered edge e u an an edge e from u to v add both u and v to e.
18:33 And the claim is that greedy is a two-approximation. Okay. And um probably won't I mean, we'll see one proof. There are many proofs. Well, we'll see a primal-dual proof, but one proof is you can say, "Look, the set of vertices uh that I pick in this way form a match um this Well, uh Look at the edges that appear in this loop throughout every iteration.
19:14 Okay? Those edges form a matching. Okay? And therefore, the number of vertices we return in our set is twice the size of a particular matching. And then you can say any vertex cover size is lower bounded by the size of any matching. Okay, so oh, you look uh I am confused.
19:35 Yeah. Uh Is that right? Okay. Yeah. For a set of size of size two, it should be a three three half approximation. Oh, yeah. Okay, well, good. So, the sets are the vertices. Right? So, vertices can have high degree. Yeah. Yeah, good. Yeah, I was I was also thinking that right when I wrote it and then I was like, yeah, the Yeah, edges edges are contained in two sets, but uh Right.
20:02 But actually, that's a good point. So, in gen- for set cover for set cover, um we said that if every set has size at most K, you get an HK approximation, like a log K approximation. But you could look at the other way around, too. You could say, well, what if every element is contained in at most K sets? So, for that, you could get a K approximation. And how's that?
20:20 Well, actually, it's going to be related to what I'm going to write now. So, uh proof, you know, if you really want to see one proof, we'll see another one. Uh one proof, you know, see you know, see the CS 124 notes so I'll Google it or something. But uh I'll show you a different proof.
20:40 Today, we'll do primal dual. Um but other proof is primal dual. That's going to be helpful for something on the P set that will come out soon. So, let me write the LP an LP relaxation now, not the LP relaxation. So, primal the primal is um minimize the sum I equals 1 to N or the sum V goes from 1 to N of X of V.
21:15 So, that's whether or not you take the vertex V into your vertex cover. Subject to for all edges for all edges E being UV in the set of edges, XU + XV is at least 1 and X is at least 0 entry-wise. I mean, this should look familiar.
21:43 It is it is the set cover LP basically. Uh dual want to maximize the sum over edges of Y sub E such that for all vertices V um the sum of and edges containing V of Y sub E should be at most 1. And also Y is entry-wise at least 0.
22:32 Okay, so another way besides greedy, so the nice thing about the greedy algorithm is that it's pretty fast. You don't have to actually solve any linear programs. If you're willing to solve linear programs, which is slower you could just solve this primal. Right?
22:49 And you could say, well I'm going to get now some fractional solutions for the XUs. Right? And what I'll And then what I'll say is, look, for every for every one of these Now, I need to get an integral solution. I you to choose which vertices to actually pick. For one of the For every one of these inequalities, either XU is at least a half or XV is at least a half.
23:10 Okay? So, I'll pick whichever one is uh whichever one is at least a half, I'll put it into my set. Okay? And you've now at most doubled XV, so you've at most doubled the the cost of the solution.
23:30 So, that's a two appro That's another two approximation for set for uh for vertex cover, and that's also a K approximation for set cover if every set is contained in K elements. Right? Because if every set is contained in K elements, remember these are the sets. You'll have a constraint here that involves K variables.
23:45 Their sum is at least one. One of them has to be at least one over K. So, take the one which is at least one over K. And then now you'll get a K approximation. Okay, so that's it. So, I want to show though a primal-dual analysis of the combinatorial algorithm.
23:59 We like combinatorial algorithms because they're faster than actually solving linear programs. So, um so going back here, so now the proof using primal-dual. It's again going to be dual-fitting. When greedy takes you takes you takes some vertex V in capital V, set XV to one.
24:28 And also uh set X Sorry. When greedy decides to cover an edge E, when greedy covers an edge E, which is UV in the edge set, uh set XU and XV both to one. Actually, this isn't even going to be dual-fitting. This is just pure primal-dual cuz we're going to get feasibility automatically. Set uh and set Y sub E to one.
25:09 Okay. So, I think that's it. So, um Both of these are feasible solutions. Okay? And whenever we increase the dual solution by one, we increase the primal by at most two. Possibly one if one of them was already taken. So, it's a two approximation.
25:44 Okay? So, both feasible, but primal cost is at most twice dual cost. Applies to approximation. So, on the P set, you'll see the case where the vertices are actually weighted. So, you're trying to minimize XV times the cost of V. Then you need to think about what the greedy algorithm needs to change.
26:15 You know, are you still going to take both? That's probably not a smart idea if one of them is way cheaper than the other one. But, um by reasoning about both the primal and the dual, you can get, you know, a decent algorithm.
26:37 Okay. So, that's all I want to say about approximation algorithms via dual fitting or via primal dual. Um I want to move on to item two, which is integrality gaps. Okay? So, we can ask ourselves we can ask ourselves uh you know, what is the limit of using some uh LP relaxation?
27:14 Well, if you think about it, we always so far we achieve we we in our proofs we say we achieve cost at most some approximation factor alpha times the opt of the LP relaxation. Right? And we can ask ourselves, well, can we improve alpha from log n to root log n or to a constant or something? But, what if there's an inherent gap between the opt of the LP relaxation and the opt of the original integer program? Right?
27:51 So, if there is some gap So, let's say we're looking at a minimization problem. If there is some gap uh that says opt of the LP is at most, you know, beta times opt uh beta times opt of the uh
28:23 integer program for some particular instance, some particular input, you know, then such an argument we can't hope to get uh better than a beta approximation. Then we cannot hope to achieve a ratio alpha which is strictly less than beta. Right?
29:01 So, I mean, I don't want to say that we can't hope to achieve it um via any algorithm, but we can't achieve it via this particular LP relaxation, which goes back to your question. Um which is, you know, when you said it is the LP relaxation unique? You know, it's not. Sometimes if you're smarter and write down a better integer program to begin with, right? There might be many different ways to capture the problem as an integer program.
29:27 If you write it in a smarter way and then do an LP relaxation of that, maybe that could maybe a different LP relaxation could give a better approximation ratio. But this just this just gives you a limitation on using a particular LP relaxation. Okay? So, for example, I mean, let me let me make this concrete example.
29:45 Let's go Let me do them back in reverse order. First, I'll do vertex cover cuz it's simpler, then I'll do set cover. So, vertex cover. So, where's the LP for vertex cover? It's right here. So, what this constraint actually should have been is that Let me write it like this.
30:08 For all for all U, XU is at least zero. What this constraint should have been is that XU is either zero or one, and we relaxed it to this, right? And I claim that actually once you do that relaxation, you you already are losing a factor of two.
30:27 There inputs where beta is two. Okay? Or roughly two. Where opt for the fractional solution is only half the cost of opt for an integral solution. Okay? So, what's an example? Uh take the complete graph on N vertices. Uh I'm not going to draw any complete graphs. That was terrible.
31:03 This doesn't even look right. Okay. And I think I drew one twice. I should have drew two twice. All right. So, I forgot it's a Yeah, yeah, okay. That makes sense. Okay? So, opt of the fractional of the LP relaxation, well, what can we do?
31:34 We can put a half on every vertex. Right? That would be a feasible solution. In fact, that is that is the optimal solution. That's N over two. A half on each vertex. Whereas in the integer program, I mean, for the actual vertex cover problem, the best you can do is N minus one.
32:05 Okay, you take some vertex you just take take one vertex uh Right. Um take all vertices except one. So, N minus one. Right? So, if you take any solution with fewer with N over two or fewer vertices that means there at least two vertices left out but then you're not covering the edge between them. Okay, so you need a cost at least n minus one.
32:47 So there's a gap of roughly two. Okay, so if you're arguing using this LP relaxation, if you're somehow rounding solutions to that then you know, you're you're sort of out of luck. Yeah. Yeah, so I'm saying if if if our if our way of if our way of coming up with this algorithm and analyzing it is to compare with the optimal solution of some LP relaxation,
33:32 well, if the if if the LP relaxation has a gap with the original integer program and that gap is at least a factor of beta, then there's no way to achieve better than a beta approximation by this kind of comparison, right? Like if if the way that we're analyzing our algorithm is to say, "Look, our algorithm never achieves cost more than alpha times opt of the linear program."
33:58 Well, you're not going to be able to achieve an alpha here that's better than beta because the solution you're providing is an integral one. Right? So in particular, the example which creates this gap, you're going to have you're going to be off by at least beta. Right? So So that's what I mean.
34:20 Um So yeah, this the best beta you can achieve is usually called the integrality gap. It's like the the max over all instances of the of the of the gap. Um and usually you parameterize instances by something like the by the problem size. So like it as a function of n, what's the worst gap that you could possibly have?
34:44 Or as a function of some other parameter of the problem. So we're going to see that for example for set cover. Right? There we're we're going to parameterize by n and we're going to say as a function of n, what's the worst gap that you can have? So I mean we're going to give an example where you're off by a log n. Okay.
35:06 So in this case the gap The 2n - 2 over So yeah, here I'm really looking at the ratio. So yeah, it's it's as n gets big the gap is approaching two. Any other questions? Okay. Oops. Okay, so for another example, this one will be a little more a little trickier.
36:00 Set cover. I want to give a log a log n gap. Define n to be 2 to the Q - 1 for some integer Q bigger than zero. Okay. And elements of uh of the universe are in correspondence with elements of F2Q without zero.
36:49 So, what is this? These are vectors of length Q. Um over F2. Yeah, over 0 1. So, this is a vector space. Hey, so really I'm just saying, you know, think of these as like bit strings of length Q and adding them means bitwise uh bitwise XOR.
37:25 And sets are uh also in correspondence with elements of F2Q where the set corresponding to alpha, so let's say if alpha is in F2Q, so it's also some bit string of length Q, that implies that S sub alpha
37:57 is the set of all E in the universe such that alpha dot uh E This is the dot product is equal to one mod two. Okay? Are there questions about, you know, feel free to if I'm saying if I'm using some jargon that's uh that doesn't sound good to you, just ask me to clarify, okay?
38:28 Yeah. Like so I think that beta is one over alpha, right? Like take the reciprocal. Oh, uh is that right? So Oh, yeah, yeah, yeah. I see what you mean. You can't hope to achieve alpha. Yeah, okay. Yeah, so opt of the IP.
38:59 If opt of IP is greater than or equal to one over beta opt of Right. Yeah, okay. Yeah, right. So let me just think. So here, so if the LP is one, the IP is two. Oh, yeah, okay. So this beta is actually a half. Yeah. Yeah, okay.
39:24 Yeah, good. So So this one over beta is what I was calling the integrality gap, okay. Very good. Yeah, thanks. All right, so here I have a vector of bits, here I have a vector of bits. I'm taking their dot product. Okay, mod two.
39:53 Okay, good. So what am I going to try and claim? I want to claim that a fractional solution can actually cover all the elements with a cost of a constant. Okay. Whereas an integral solution has to have cost at least Q. And Q is about log n.
40:14 So what's a fractional solution? What's a cheap fractional solution? Let me ask you let me ask first as a hint. For every element in the universe, how many sets contains it? How many sets contain it? Okay, so there are two to the cube sets and wait, how many how many contain it? There are two exactly two to the cube sets.
40:47 Half of them, right? Because in particular, I mean one easy way to see that is if you pick alpha at random, then the probability that this dot product is one is a half. Right? I mean and that's because we removed zero from the universe. So, each element is contained in exactly half the sets.
41:21 So, that implies we a feasible solution is can take that for all U, XU is uh two over M. Okay. Good. And what's the cost of the solution? It's two. Implies the opt of LP is at most two. Just make sure we're all on the same page, right?
42:07 The the cost of in the LP was just the sum of the XUs. And the constraints were that for every element, the sum of the XUs for you uh for all S, I should say, for all sets S, XS is 2 over M. So, the constraints are that for any element E, the sum of all the X S's for S containing E should be at least one. Okay.
42:30 So, this is just equal to uh one over the number of sets containing uh E. for some E. Okay, so good. Meanwhile, for the integer integer solution, Okay? Well, it's going to follow from linear algebra. Right? Suppose we have a solution with Q minus one sets, S alpha one up to S alpha Q minus one.
43:29 And what you're telling me, you're telling me that the union of S alpha I or the intersection of the complement of S alpha I, where I goes from one to Q minus one, you're telling me this is the intersection is empty. There's nothing that's not There's nothing that's uh not covered by any of them.
43:54 Okay? But, what is what does this mean? What is this intersection? This equal to the set of all E's or not that it's uh uh empty but that I guess it's the set it's the set zero. Zero is in Yeah, it's not in the universe. Yeah. So, what is the set?
44:25 It's the set of all E's such that um for all I from one up to Q minus one alpha I dot Q uh dot E is equal to zero. Right? So, we started off with a Q dimensional space, a Q dimensional vector space. And here, this is the set of all elements satisfying Q minus one constraints.
44:55 Q minus one linear constraints. So, its dimension is at least one. Okay. So, in particular, it's non-empty. This is an at most Q minus one dimensional space. Uh sorry. So, sorry, not that's not what I meant. Q minus one linear constraints implies it's at least one dimensional.
45:32 Which implies it's non-empty. Okay. So, that's a contradiction. So, you need at least Q sets. Okay. Questions? Okay. So, now I want to touch on the last thing, polynomial time approximation schemes. So, here the idea is Well, let me just start defining start defining some of these terms.
46:21 So, let me look at minimization problems. You can define similar things for maximization problems. Okay. We say a problem admits a PTAS. This is a polynomial time approximation scheme. Actually, you know, just before I just before I um Let me let me say one more thing before I finish with with uh integrality gaps.
47:13 There are actually stronger things you can do. So, with integrality gaps, you're just saying that this particular LP relaxation can't give me something better. You know, a stronger statement that you could hope to make is unless P equals NP, there's no polynomial time algorithm to do better than a log-in approximation.
47:37 Okay, right? So, I mean, forget about even using LP relaxations at all. No matter what you do, unless P equals NP, there's no better better uh approximation ratio achievable. So, actually, for the set cover problem, it's known This is due uh theorem due to Feige in '98
47:55 that you can't you can't really do better than natural log of n unless you can solve SAT in time n to the log log n or something like that. Okay. The best known algorithms we have for SAT run in exponential time in n. n to the log log n is way cheaper than that. So, that gives strong evidence that um we don't we we don't expect to beat, you know, let natural log of n.
48:23 Um so, that the proof of that doesn't use any it uses some machinery that we're not going to cover at all in this class, namely it builds upon something called the the PCP theorem. PCP stands for probabilisticly checkable proofs. Um I guess if you want to hear about that, take a complexity course or go read about it, okay.
48:42 Um anyway, I just thought I would mention it. You should be exposed to its existence. Okay, so so back to PTASes, FPTASes, and FPRASes. So, we have some minimization problem, set cover or whatever else uh vertex cover, etc.
49:01 And we say it admits a PTAS if um for all epsilon in 0 1 and also for all problem sizes n can achieve uh we can achieve um for all epsilon fixed can achieve 1 + epsilon approximation in time poly n.
49:45 We write it as n to the f of 1 over epsilon. Okay? So, think of epsilon as a fixed constant, .1 or something. Okay? So, what I'm saying is for any fixed constant epsilon you give me, then it's possible there is an algorithm that gets a 1 + epsilon approximation and this time f of n f of 1 over epsilon could be terrible.
50:22 Okay? It It doesn't have to be polynomial in 1 over epsilon. It could be 2 to the 2 to the 2 to the 1 over epsilon or something. But, if it's a fixed constant, then this is a polynomial. Okay?
50:36 So, meanwhile in FPTAS, F stands for here fully. So, a fully polynomial time approximation scheme is one where uh for all epsilon, we can get time polynomial in n over epsilon. So, you're not allowed to have crazy dependencies on epsilon. In particular, epsilon, you know, you shouldn't have uh epsilons in the exponent of n.
51:35 And in FPTAS, is a uh fully polytime randomized Well, there's no I guess it should be F P tras, but you can't really pronounce that. approximation scheme and um Here we allow ourselves to use randomized algorithms. And these randomized algorithms are allowed to have some probability of failure.
52:16 So So the time is poly n over epsilon but allowed to give a wrong answer meaning not uh not wrong answer, but say not achieve 1 plus epsilon opt with uh probability at least the probability at most a third or something. Ah, good question. Why a third?
53:02 So suppose I could achieve this third guarantee. And I really wanted to achieve a guarantee of say delta as opposed to a third. So what would I do? Make a bunch of different runs, right? And take like the the median run or something.
53:24 Okay, so um So basically this the way you define it uh when you define this F P tras, the way you specify that constant doesn't really matter. Yeah. I guess uh Why is that the case? Well, maybe not in this situation. So, uh A third is a good thing for kind of bounded uh error polynomial time algorithms.
54:06 Uh maybe What's one nice thing about a third? So, suppose Forget about F Prases. The reason I The reason I pick a third, I'm now digressing slightly, but the point is if you have an algorithm that outputs a number and you have no way of verifying that that number was correct or not, okay?
54:22 Well, if you know that the the number is is failing you with probability at most a third, then if you take many trials and take the median number that showed up, it'll be good with probability with high probability, okay? Um that's not true with a half, right?
54:40 Uh Um So, a third is sort of the the number of the form one over integer, where integer is as small as possible, which works. Okay, so. Uh Yeah. Okay, so good. So, I want to show examples of P Tases and FP Tases and F Prases. So, I'll show a P Tase and I'll I'll also show an FP Tase for knapsack.
55:15 And I'll show an F Prase for counting number of solutions to a DNF. I forgot the year. This is uh So, this is due to Karp Luebke and Madras, I believe. And I I'll I don't remember the year right now. Knapsack, well uh there's there's been a sequence of papers.
55:51 I'm not going to cover the most efficient uh FP tasks or P tasks, but from searching around it seemed that the most efficient one most efficient FP task for knapsack was due to Eugene Lawler in '79. But maybe I missed some reference. Okay.
56:21 These are examp- This is what I should have said. I should have said these are examples. Okay, so uh So, let me define knapsack. So, we're given So, we have a knapsack with capacity W. And we're also given items with weights W1 up to WN and values V1 up to VN.
57:18 Yeah. Can you just remind what the knapsack is? I'm defining the problem. Oh, okay. I thought This is the definition of the problem, sorry. Yeah, prob- So, problem statement is this, okay? So, So we have a knapsack uh with capacity W.
57:39 Knapsack I mean I literally mean a knapsack like we have a backpack, okay? And it can hold W pounds worth of stuff. And we have items with the following weights. So item I has weight WI and value VI. And we want to pack our knapsack to maximize the total value.
58:11 So this is this is our goal. Okay. So So we can write it this as maximize sum I from 1 to N of the value of item I times XI which tells us whether we took it or not
58:41 subject to the constraint that uh the sum I from 1 to N of WI XI is at most W and that for all I WI is either XI is either 0 or 1. Okay, so this is knapsack. So what So suppose we relaxed the integral constraints this integral constraint to um Suppose we relax this I like this one.
59:23 This color is more visible I think. So, suppose we relax this to xi is between 1 and 0. Okay? I don't want to relax it to just say xi is bigger than equal to 0 because if there's a really valuable item, you might be incentivized to take it multiple times. Okay?
59:45 Which I There is a variant of knapsack where that's allowed. I think it's called multi knapsack or something, but for me, you can't you can't purchase multiple copies of the same item. Okay? You can just take a subset of the n items you're given. So, suppose you had this fractional version of knapsack, what would the optimal solution be?
1:00:06 What would you do? Yeah, so for fractional knap For fractional knapsack, sort items in decreasing order by vi over weight of i. So, which has the best Which gives you the most bang for your buck, most value per pound. And take a fill up fill up knapsack uh in this order, right?
1:00:54 So, put as much of item one in this sorted order as you can, and if you still have space, put item two until you run out of space. And on the last item, you might only be able to take a fraction of it, but you'll take whatever fraction you can fit. Okay?
1:01:10 So, what's a natural What's a natural greedy algorithm that you might hope So, by the way, uh knapsack is NP-hard. Okay? Um but I claim that there are dynamic programming solutions to knapsack. Right? So, So, exact integral knapsack One thing you can do is you can get a time um O of N W.
1:01:48 Okay? So, here what you do is you say F of I W is equal to the most value achievable. Let me Let me make myself some Let me not cram myself. So, what do you How do you get this? You say F of I W is the max value achievable All right, let me let me write it as B.
1:02:18 F of I B is the max value achievable if we have B space left and only take items from the set from the set one up to I. Okay? So, at the end of the day what we want is F of N {comma} W. How do you get F of I {comma} B?
1:02:53 Well, you can either take the I'th item or not take it. So, you can either F of I B is equal to the max of F of I minus one B, where you don't take the item, or F of I minus one or So, let me write it like this. F of I B is equal to zero if I is equal to zero.
1:03:15 Otherwise, it's equal to the max of f of i minus 1 b and vi plus f of i minus 1 b minus wi if b minus wi is not negative. So, you can write a recursion like this. Okay? And fill up this table using dynamic programming. So, So, great.
1:03:44 We have a fast algorithm for knapsack, but I but knapsack is NP-hard. How's that possible? Yeah, double Yeah, W is Right, when we say polynomial time, we mean polynomial time in the bit representation of the input. Right? And W to write down W as part of the input takes log W bits. So, to actually be polynomial time, we would have to spend Polynomial time means polynomial in n and log W.
1:04:12 So, n times W is not acceptable. And you can also get So, you can also define v to be the sum over i of vi. And you can can you can also get time O of nv. That's another thing you can do for knapsack. How is that?
1:04:42 You define f of i {comma} uh p as being It's another dynamic program. Any Has Have people seen this uh Right? How would you get? So, nw for knapsack is according to this. You could also get nv. Any uh How would you define f of i {comma} p? Yeah.
1:05:11 Uh you want weights Minimum weight to get value exactly V using only items from the set one up to I. Okay, and I'm not going to do it. You can set up a recurrence to fill this table out as well. Uh I um I think they're just they're just different algorithms.
1:05:47 Yeah. Yeah, I think they're just different algorithms. Okay, so great. So now what we want is we want an approximation algorithm. So what's the So okay, so we know how to do exact integral knapsack. And we know how to But it's slow, right? We don't like W. We want log W. And we know how to do exact fractional knapsack.
1:06:17 So what's a natural greedy algorithm that the exact fractional knapsack suggests to us? Yeah. So uh approximation algorithm attempt for integral knapsack. Sort by V I over W I. Keep taking items till there's no space. Okay. So I claim though that we're we're going to have to tweak this algorithm, but I claim that just as written we can do very badly.
1:07:17 Anyone have an an example of an input where we would do badly? Yeah. Right. So, you're saying um there might be an item that has a better ratio which has a very small very small weight and very small value, but just a better ratio, but then there's a big item that has a lot of weight that once you put the first item you can't fit it.
1:07:53 Right? So, that's that's right. So, for example, bad case. Uh you could imagine for example, V1 = 2 and W1 = 1. Whereas V2 = uh W and W2 = W. Right? So, greedy would take this item first cuz it has the better ratio, but then you can't fit this one. Um so, this is whereas optimal would have just taken V2 and gotten W value.
1:08:35 So, this implies that you get an unbounded or really you know, uh not better than And I could have made this, you know, 1 + epsilon. Not better than, you know, a W approximation. And so, that's not great. And here's a modified greedy algorithm that I claim does pretty well.
1:09:29 Take either one, the output of greedy, or two, the most valuable item. I'm pretending I'm imagining that I've already filtered out items that have weight bigger than W. I mean, if a If an item has weight greater than W, there's no reason to acknowledge its existence.
1:09:58 Okay, so claim is that this algorithm is a two approximation. Okay? And we're going to prove a lemma, and then we're going to see how to exploit that lemma to get a PTAS. Okay, so let me write a lemma here, lemma one. Suppose greedy takes items.
1:11:03 Uh V1 over W1 greater than equal to V2 over W2 greater than equal to greater than equal to VK - 1 over WK - 1 then no room for uh Kth item. Then the sum I from 1 to K of VI is at least opt.
1:11:50 Okay, that's the lemma. So, proof. The proof that greed modified greedy is a two approximation Well, I claim it follows immediately from the lemma. Why is that? Are people okay with the statement of the lemma? Yeah. I'm sorry, say that again. Yeah.
1:12:38 Yeah. Yeah. Right. Right. Right, I mean Right. I mean All right, another way of saying the same thing that you just said is the sum of VI from I is one to K is just uh V1 plus dot dot plus VK minus one plus VK. So, one of these is at least opt over two by the lemma.
1:13:16 Okay? Okay, so that's that's the proof. So, now we just need to prove this thing. So, how would you prove this lemma? And I claim uh you should think about this thing. Yeah. So, we know that the fractional knapsack has has any weight. And the value of the fractional knapsack is the sum of the first K minus one item plus fraction of the last.
1:14:05 Yeah, exactly, right? So, so we know we know what opt is for this thing, right? Opt for this thing would take the first K minus one of these items, and then it would take some fraction that's less than one of the last item. Okay?
1:14:25 So, we know that that that's the opt That's what opt opt would get, the optimal profit for the fractional solution. And we know that the integral opt can be at most the fractional opt. And this number is at most This number is bigger than the fractional opt, right? Cuz we're not just taking a fraction of the Kth element, we're taking the whole thing. So, proof is that the sum I equals 1 to K of VI is even bigger than fractional knapsack opt.
1:15:07 Okay, so that's it. Okay, so now I want to give a PTAS. Okay. And I think the main observation that I want to use for this PTAS is that if if no item has value bigger than epsilon times opt then greedy achieves at least 1 minus epsilon opt.
1:16:30 Okay. Um yeah, so I should say I defined PTAS, FPTAS, etc. for minimization problems, but you could also define them for maximization problems. So, minimize with the minimization problems, you want to get at most 1 + epsilon opt. For maximization, you want to get at least 1 - epsilon opt. Okay? So, why is this true? Right?
1:16:51 This is true because of the lemma. Right? So, greedy gets the first k minus one things in this sum and misses out on the kth. But, if no item has value if no item has value more than epsilon times opt, then missing out on the kth is at most losing us epsilon times opt.
1:17:12 So, the sum of the first k minus one is at least 1 minus epsilon opt. Okay? So, also, this is observation one, observation two is at most 1 over epsilon items can have value um at least epsilon opt. Or bigger than epsilon times opt.
1:17:50 Uh now, well, wait. What do I mean by that? At at most 1 over epsilon items in the optimal solution have value bigger than epsilon opt. Right? Otherwise, opt would be better than opt. Okay, so, now, what's a PTAS? Remember, epsilon is a constant. Okay?
1:18:18 So, what what's Give me some algorithm that, given a fixed epsilon, runs in polynomial time. Your exponent is allowed to behave as you want in terms of epsilon. It take a minute to schedule the Yeah. Yeah, exactly. So, the algorithm So, just to repeat what Yarik said, this is just an algorithm algorithm guess a set S of size at most one over epsilon.
1:19:13 Guess a set S of size at most one over epsilon which would be the set of elements in optimal solution a value bigger than epsilon times opt. That's step one. Two, and you're going to put S in your output, okay? Uh well, you're you first we're going to check to make sure it actually fits in your in your knapsack.
1:19:47 If not, just keep going on to keep going on the loop, continuing the loop. Okay, if it does fit in your knapsack, you guessed S, then two, remove all items remaining which have value bigger than anyone in S. Right?
1:20:20 So, S is supposed to be the set of items with value at least epsilon opt. Okay, so now that we've guessed S, we can remove all the items which have value bigger than them because we're assuming that that is the set of big items. And then three, run greedy on what's left.
1:20:44 What's the running time of this algorithm? Yeah. So, n to the one over epsilon plus one. Or uh yeah, I guess there were some m's here depending on how many sets you have. So, let me just say O of m to the one over epsilon times, you know, poly of n m or something. I'll be less specific, yeah.
1:21:28 Okay. And the claim is that uh our profit is at least one minus epsilon times opt. What's the proof of that? So, suppose in some iteration in some iteration we're actually going to guess S correctly. Suppose we guess S correctly.
1:22:08 We know that opt of S uh we know that opt is equal to the value of S, so the sum of the values of items in S, plus opt prime, which is the best packing of the small items, the items with value at most with value with value at most any item in S.
1:22:38 Um meanwhile, what do we achieve? We achieve V of S plus uh greedy plus you know what greedy achieves. So, we need to show that this thing here is at least opt prime minus epsilon opt minus epsilon of opt, let's say. Okay?
1:23:04 So, greedy What do we achieve with greedy? We know that this item VK, so VK is K is the last I is the is the item that we don't take, the first item we don't take. Right? What do we know about VK? I mean we know something from here.
1:23:34 We know that Right? We know that we filtered out all the items with high value. So, we know we know that VK is at most epsilon times opt. Cuz S is the set of items containing S is the set of items with epsilon opt value for each item. And we also know that greedy the greedy output plus VK is at least opt prime. That's lemma one.
1:24:20 Which implies that greedy achieves opt prime achieves at least opt prime minus epsilon times opt. So, that's it. Okay? So, that's That's it. Questions about that? Okay. So, if there are no questions, I guess next time I'll show you an FP task for knapsack and an FPTAS for another problem. Um next week, I will not be here.
1:25:04 Uh but we'll have two guest lectures, one on Tuesday, one on Thursday. Um because I won't I won't actually be in Cambridge, I won't be here for office hours, but I'm very happy to, you know, if someone wants if people want to attend my office hours, I'm very happy to do Google Hangout or something, okay?
1:25:21 So, you should send me an email if you want to to chat. Um All right, good. And yeah, as I said, piece out four will be out tonight. Okay.