Transcript

the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit mitop courseware at ocw.mit.edu let's get started uh thanks for coming to lecture now there's a quiz coming up there will be a tangible benefit of attending this lecture uh and it's not frisbees okay we'll figure it out soon um so um two lectures on um approximation algorithms uh one today and uh one uh I guess a week and two days from today on Thursday after the break uh Eric will give that one so this is more of a introductory lecture Eric talked about uh NP complete problems and NP hard problems uh he talked about how you could show that problems uh are NP complete or NP hard so what happens when you discover that a problem is NP complete or NP hard well there's a variety of uh strategies uh you could just kind of give up and say this is intractable I want a different job uh you could uh say that I'm just going to uh do the best I can without any theoretical guarantees uh I'm going to use a heuristic I'm going to think of this simplest greedy heuristic I'm going to code it up and I'm going to move on um or you could do approximation algorithms you could uh you could say I'm going to think up of a interesting greedy heuristic but I'm going to prove uh that this greedy heuristic in every conceivable situation with respect to the inputs is going to be within some factor of optimal right and that's what we're going to do today we're going to take a bunch of NP complete problems and we're going to essentially create create uh simple heuristics for these problems simple strategies that are polinomial time to quote solve these problems and uh what does it mean to solve these problems well you know that if it's polinomial time you're not guaranteed to get the optimum answer every time but you'll call it a solution an approximate solution because you're within a factor of two for every possible input that's one example or you have a more complicated approximation factor that we'll get to in a second where it's not quite a factor of two might be a factor of two for small size problems might be a factor of 10 for larger problems and so on and so forth and then the last thing is it'd be great if you could spend more time and get better Solutions and those are approximation schemes and we'll look at an approximation schemes as well right so just dive in each of these problems depending on whether it's decision or optimization is NP complete or NP hard I'll Define these problems as we go along but basically the name of the game here is uh grab a problem Define it uh think of a interesting heuristic uh do a proof okay and that's uh essentially what we're going to do three times uh the good news is the proofs aren't tortous they're not 30 minute proofs uh and they should be pretty intuitive and we'll see if we can extract them out of you a painful extraction process I went to the dentist yesterday not for extraction I should have said I went to the dentist yesterday and I'm now going to take it out on you right okay so what's an approximation algorithm an algorithm for a problem of size n and so it's going to be parameterized and the approximation Factor may also be parameterized it'd be nice if it weren't that it was a constant Factor approximation but sometimes you can't do that and in fact sometimes you can prove that constant Factor approximation algorithms don't exist and if they do then P equals NP right so it's uh gets very interesting so in this case approximation algorithms or schemes exist for these three problems which is why we looking at them today but you got a problem of size n and we're going to Define an approximation ratio row of n for any input uh if for any input excuse me the algorithm produces a solution with c c that satisfies this little property um which says that the max of C ided by C op divided by uh sorry and C op divided by C is less than or equal to row M right and the only reason you have two terms in here is because you haven't said whether it's a minimization problem or a maximization problem right so if it's a minimization problem you you don't want to be too much greater than the minimum if it's a maximization problem you don't want to be too much smaller than the maximum and so you just stick those two things in there and you don't worry about whether it's Min or Max in terms of the objective function and you want it to be at that particular ratio okay now I did say row of n there so this could be a constant or it could be a function of n if it's a function of n u is going to be an increasing function of n okay um otherwise you could just bound it and have a a constant obviously so um you might have something like and we'll see one of these log n approximation scheme uh which uh which says that uh uh you're going to be within logarithmic uh of the answer minimum or maximum but uh if it's a million then uh if you do log of base two then you know you're within a factor of 20 uh which isn't that great but let's just say we happy with it and then if it goes to a billion it's a factor of 30 and so on and so forth right so it could grow so that's an algorithm um that these terms are are used in changeably uh we'll try and differentiate but we do have something that we call an approximation scheme and the big difference between approximation algorithms and approximation schemes is that I'm going to have a little knob in an approximation scheme that's let going to let me do more work to get something better okay and that's essentially what a scheme is where we're going to take an input an additional input Epsilon strictly greater than zero and for any fixed Epsilon the scheme this is an approximation scheme as opposed to an algorithm is a 1 + Epsilon approximation algorithm and so here we just say that this is a row N approximation algorithm if it satisfies this property and here we have a family of algorithms that are parameterized by n in terms of runtime as well as Epsilon and so um you might have a situation where you have order n raed to 2 / Epsilon running time for an approximation algorithm and what this means is that if you're within 10% of optimal then you're going to put 0.1 down here and this is going to be an N raised to 20 algorithm polinomial time wonderful solve The World's problems not really I mean end R to 20 is pretty bad but uh it's not exponential right so you you see that there's a there's a a growth here of um polinomial degree with respect to Epsilon and it's a pretty fast growth if you want to go to Epsilon equals 01 I mean even n ra to 20 is probably untenable but certainly n ra to 200 is is completely untenable right so this is what's called AAS which is a probabilistic time approximation scheme and don't worry too much about the probabilistic it's a function of um of Epsilon that's the way you want to think about it the runtime and we'll look at a particular scheme later in the lecture but clearly this is a polinomial in N okay but it's um not polinomial in epsilon all right so a ptas is going to be poly in N but not necessarily in epsilon and I say not necessarily because uh I we still call it a p Tas we just say fully polinomial time approximation scheme FP task if it's polinomial in both n and 1 / Epsilon right so fully P test is poly in n and 1 / Epsilon so a fully P scheme would be something like n / Epsilon Square okay so as Epsilon shrinks um obviously the runtime is going to grow because you got 1 / Epsilon square but it's not anywhere as bad as the N raised to 2 ided Epsilon in terms of its growth rate okay so there's lots of NP complete problems that have ptases and that some of them have FP tases as well and so on and so forth question what does the what problem um so we won't get into that uh today but you can think of it as um um as uh the the the the probability uh over the the space of um possible solutions that you have uh you can you can distribution of uh distribution of inputs it that the bottom line is that we actually won't cover that uh today so let's shove that for uh uh for next lecture okay so just worry about the fact that um this this it's uh uh it's a polinomial in n and uh not in epsilon for the first part and it's polinomial in n and Epsilon for the second part okay oh I see so this a good point so for this the purposes of this lecture thank you so much uh I'm glad I didn't have to get into that polinomial time good better answer either way we're not going to cover that all right good so it's polinomial I mean you could have probabilistic algorithms that have this kind of um uh behavior of course uh but we're not going to cover that uh in today's lecture but thanks for pointing that out Eric uh so that's our setup uh we essentially have u a situation where it'd be great if we could tackle NP complete problems using this uh hammer right uh any questions so far all right vertex cover so let's Dive Right In I talk about uh a particular problem very simple problem uh what you have is an undirected graph gve and all we want is a set of vertices that cover all of the edges so a set of vertices that cover all edges what does it mean to cover it's the obvious thing if I have something like this as long as I have a vertex in my set of vertices that I'm calling a cover that touches one end point of an edge we're going to call that edge cover okay so in this case it's a pretty clear that the vertex cover is simply that because that vertex touches all of the edges at least uh one of the end points a Vertex is going to touch one end point of an edge but this uh vertex cover that I've shaded touches every Edge right so that's a Vertex cover um if in fact I had an extra edge here then um I now have to pick one or this one or that one in order to complete my cover okay that's it that's vertex cover um decision problem uh and NP complete uh to figure out if there's a certain number uh that uh is below a certain value that do do the covering uh uh you obviously have an optimization problem associated with that and so on and so forth so that's our simple setup for our first hard problem right um and so just write that out find the subset V Prime which is a subset of capital V such that if UV is an edge of G or belongs to e then we have either U belonging to V prime or V belonging to V prime or both it's quite possible that your vertex cover is such that for a given Edge you have two vertices that touch each of the end points of the edge and the optimization problem which is what we'd like to do here is find a v Prime so the cardinality is minimum okay so that's it so we don't know of a polinomial Time algorithm to solve this problem so we resort to heuristics what is an intuitive heuristic for this problem suppose I wanted to implement a poly time greedy algorithm for this problem what would be the first thing that you think of yeah go ahead find a Max degree I love that answer it's the wrong answer but for this problem but I love it because it sets me up for all this work I did before lecture okay all right so um it turns out that it's not an incorrect answer I it's uh it's it's really not the best answer in terms of theistic you apply to get an approximation algorithm so we're we're still in in the context of an approximation algorithm not an approximation scheme and uh what we have here is a perfectly fine heuristic that you know who knows it might actually work better in practice than this another approximation algorithm that I'm going to talk about and prove but the fact of the matter is that this approximation algorithm that has as a heuristic uh picking the maximum degree continually and uh completing your vertex cover by picking the maximum degree continually is uh a log n approximation algorithm and what that means is that I can construct and that example is right up there and a an example where um regardless of of what n is U this particularistic the maximum degree heuristic might be Logan off from optimal okay whereas this other scheme that we're going to talk about is going to be within a factor two of optimal regardless of the input that you apply right so so you have a domination here with respect to the two approximation algorithms you got one that is log n row N is log n as I've defined over there and on the other side you got two right so if you're a theoretician you know what you're going to pick right you're going to pick two now it turns out if you're a practitioner you might actually pick this one right but you know this is a theory course um so what is going on here well this is a concocted example that shows you that a maximum degree heuristic could be as far off as um as Logan right and so if you look at what's going on here um you end up uh with um with with something where you have a bunch of vertices up on top okay and uh you you end up with case K factorial vertices up on top so k equals 3 in this case so I have six vertices up there um I got two down here because this is 6 divided by three because K is three and then I got six divided by three here so that's two and six divided by one here and so that's six okay and so these edges are set up in such a way that U it's a pathological example um and I I misspoke in terms of the approximation algorithm I'm I I'll correct myself in just a second in terms of log it does does grow with u uh with with the size of the graph but I'll precisely tell you what this uh approximation algorithm is in terms of the row and factor in just a minute but let's just take a look at um this problem here and see what happens when you apply this maximum degree heuristic right and we have to take into account the fact that if you have ties in terms of Maximum degree you may end up doing the wrong thing because you haven't defined what the tiebreak is when you have two noes that have the same degree you could do the wrong thing and pick the bad node for this particular problem right you have to do a verse case analysis right so um in the worst case when you create a Vertex cover using maximum degree what is the worst case in terms of the number of vertices that we pick for this particular example so what is the worst case in terms of the number of vertices yeah back there 11 11 and where did you get that from all the bot you grab all of the ones on the bottom fantastic right there you go could you uh stand up yeah whoa all right it was the dentist yesterday um so uh that's exactly right that's exactly right so what could happen is you could pick this because that's degree three notice that the maximum degree here is three of of any note right so if I pick something of degree three I'm good I'm in keeping with my heris um I could pick all the ones at the top right and then I'm done right that's good uh that's a good uh Solution that's a a good trajectory but all I've said is theistic is maximum degree so there's nothing that's stopping me from picking this and then once I pick that I could pick this one and then I'm down to once I've taken away these two remember that now the maximum degree in the entire graph is two right because I've each of these things is losing a degree losing one from its degree as I go along so then I could pick this one this one this one Etc and so I could end up with 11 okay so if you go do the do the math really quickly and this is where I'll I'll I'll correct uh what I said before um the algo could pick all the bottom vertices and so the solution uh and the top vertices are optimal top optimal so that's K factorial right according to my parameterized graph that's K factorial in terms of the optimal solution for this graph but if I pick the ones that are uh that are at the bottom then it's K factorial divid 1 / k + 1 / K - 1 plus da d d da + 1 which is our harmonic number and that's approximately K factorial log K okay and and this is where I misspoke I kept saying log n log n but that's not completely correct because um if I think of n as being the size of the input uh K factorial is n right um and so if you see that I have log K here uh then um remember that um this is log K where where K factorial equals n so there's another log Factor roughly speaking right so think of it approximately as log log n approximation okay so which is pretty good but it does grow with n right the point is this does grow with n so it's not the best approximation scheme that you can think of uh because uh the approximation Factor grows with the size of your problem so it'd be great if we could come up with a constant Factor approximation scheme that would beat this one certainly from a theoretical standpoint right but this one maximum degree chances are if you're a practitioner this is what you you'd code not the one I'm going to describe okay but we're going to analyze the one I've described I've just shown you that there is an example where uh you have this log K Factor but we haven't done a proof of the fact that there's no worse example than this one okay so I'm just claiming at this point that uh this is at best a a log K approximation algorithm we haven't actually shown that it is in fact a log K approximation algorithm at best it's that okay uh any questions all right so what's another heris what's uh what's another heuristic for uh doing vertex cover we did this uh picking the maximum degree nice and simple but didn't quite work out for us any other ideas so I picked vertices what else could I pick I could pick edges right so I could pick I could pick random edges it turns out that actually works better from a theoretical standpoint uh so what we're going to do here is simply uh set the cover to be null go ahead and set all of the edges to be e Prime and then we're going to iterate over these edges I'm not even specifying the way I'm going to select these edges and I still will be able to do a proof of two approximation okay oh I forgot the best part this is on your quiz right that was the tangible benefit of attending the lecture so copy that down so this is very simple it's it's it's it's not a a complicated uh problem there's there's uh not simple heris that are going to be particularly complicated uh you just do some selections and then you iterate over the graph and you take away stuff from the graph typically you take away vertices as well as edges and uh you keep going until you got nothing left right and then you look at your cover and you say what is the size of my cover and here we return C all right so I won't spend any time on that uh you can read it it's a simple iterative algorithm uh that picks edges uh randomly and keeps going okay so now comes the fun part which is we need to show that that little algorithm is always going to be within a factor of two of optimal okay and you can play around with this example and as in fact in this case you have six and 11 so that's a factor of two of course uh so even this algorithm is better than a factor of two but it won't be if I expanded the graph and increased K but that algorithm that I have up there is always going to be within a factor two and we want to prove that all right um so how do we go about uh proving that uh we want to prove in particular that approx vertex cover is a two approximation algorithm right um so any ideas how do I prove something like this where do you think this Factor two comes from right someone who hasn't answered yet you answered a lot of questions in the past right no someone all right I'm sorry the edges you pick not intersect that's an excellent observation the the observation is that the edges we pick do not intersect each other so I gave you a Frisbee for kind of the wrong answer so for this correct one I won't give you one that's fair right no that's that's unfair right there you go sorry um so the the key observation was in this algorithm I'm going to be picking edges and the edges will not share vertices right because I delete the vertices once I've picked an edge correct so there's no way that the edges would share vertices so what does that mean well that means that um I'm getting let's say I get a edges so let a denote the edges that are picked so I'm going to get edges that look like that okay and I got cality of a edges I know that in my vertex cover that obviously I have to I have to pick vertices that cover all the edges now I'm picking edges and what's happening of course is that I'm picking two a vertices so my C remember my cost was C and I had C opt that corresponds to the optimum cost and so the cost that this algorithm produces is 2 * a right Mak sense because I'm picking vertices V are picking edges there's no um overlap and therefore the cost is is 2 * a right so as long as I can now say that copt which is the optimum is less than or equal to a right I have my Factor two approximation algorithm right so that's it it's a it's a simple argument that says now show that copt is at least a um cop I'm minimizing cop should be at least a right uh I hope I said that right before but I wrote that down here correctly so if I say that copt is at least a then I got my I got my proof here of two approximation because I'm getting 2 a back right so if you go look at C divided by so this means of course that um uh C is um less than or equal to two copt if I can show uh make that statement and and it turns out that's uh a fairly easy statement to argue uh simply because of the definition of vertex cover um remember that um I'm going to have to cover every Edge correct so I'm going to cover need to cover every Edge including all edges in a a is a subset of edges I have to cover all the edges clearly I have to cover the a edges which are a subset of all of the edges right how am I going to cover all of the a edges that happen to all be disjoint in terms of their vertices I'm going to have to pick one vertex for each of these edges right I mean I could pick this one or that one but I have to pick one of them I could pick this one or that one and so on and so forth right so it is clear that given this disjoint collection of edges corresponding to a that c opt is greater than or equal to a okay and and that's it so I had to cover all this requires since uh no two edges share an end point this means that need to pick a different vertex from each Edge in a and that implies that c opt is greater than or equal to a all right any questions about that we all good here yep understood the proof so that's our first uh approximation algorithm where we actually had a proof and so this is kind of cool it was obviously a pretty simple algorithm you're guaranteed to be within a factor two um doesn't mean that that's the best juristic you can come up with um doesn't mean uh that um this is what you you'd code uh but uh this is the best approximation algorithm uh that uh we're going to cover for vertex cover okay um so what about other problems what's the state of the world with respect to approximation there's lots of uh NP complete and NP hard problems for which we know approximation schemes and we like to move towards approximation schemes slowly but I'd like to look at a problem that perhaps is a little more compelling than vertex cover before we get to approximation schemes and that's what's called set cover so set cover tries to cover a set with subsets and it's very useful in optimization where you have overlapping sets maybe it's schedules it's tasks it's uh uh people getting invited to dinner Etc and you want to make sure everybody gets invited you want to invite families and there's overlapping families because people have relationships and uh you want to uh eventually minimize the number of dinners you actually have to have and that's I don't know hopefully a motivating example if it wasn't too bad so you do have a family of possibly overlapping subsets um S1 S2 SM subset of equal to X so that's that big set that we have such that I want to cover all of the elements so that's what this uh little uh equation corresponds to the union of all the selected SI should equal uh X right I need to cover it all um and I do want to minimize called the C find C subset one 2 m so I'm selecting a bunch of these things so so C is simply Capital C here is um is some subset of the the indices and the only reason I I do that is to say that I want to do this while minimizing I want to do IAL 1 through M um while minimizing C okay oh let me get this right so that that's that this is what I have find C uh uh subset of these uh such that I'm sorry there's one more Union of I belonging to C SI equal x okay sorry for the mess here uh but so that's the line there so this is simply a a specification of the problem I'm going to be given X and I'm going to be given a large collection of subsets such that um the union of all of those subsets are going to cover X and now I'm saying I want to look inside and I want to select all of them um I have uh I want to select a bunch of these things you know C which is some subset of these indices so one may not be in it two may be in it four may be in it Etc and such that those uh uh subsets that are in this Capital C set add up to X okay all so pictorially may make things um clearer you have let's say a grid here corresponding to X so each of these dots that I'm drawing here are elements that need to be covered right so that's my X and I might have S1 corresponding to that um this is S3 right and S2 is this thing in the middle that's S2 um S5 is this one here and uh I got a little S4 over here and finally uh I got uh let's see S6 yep which is kind of this funky thing that goes like that okay so this thing here is S6 all right okay what's the optimum you got you got 30 seconds what's uh what's the optimum cover yeah go ahead you had your hand up s s yep that's exactly right so the optimum S3 S4 S5 right s S6 s oh S3 yeah S4 is this one here right S6 X5 okay good S3 and then oh you know what you're right let's let's make you right all right I don't want to erase that all right here you go um so that's three right so uh C uh would be uh cardinality of C would be three um so the it's non-trivial problem um not clear how you're going to do this I got to use a heuristic um hard in terms of optimization optimal requires exponential time as far as we know and uh we're just going to go off and say hey let's um design an approximation algorithm right so let's think of a heuristic what's a what's a good heuristic what's uh what's a good heuristic for this problem I hope I haven't scared you what's a good heuristic for this problem what's the obvious heuristic yeah the largest subset and in this particular case it's actually the best also in terms of uh in terms of theory uh so um approximate set cover at least the best that we're concerned about in this lecture and what is uh approximate set cover it's uh pick largest si uh remove all elements in si from X um and other SJ so you're constantly shrinking and then keep doing that so you I have a new problem and you're going to specify that new problem on every iteration just like we did for vertex cover and we've done many a time if you do that over here notice that U what you end up uh with is is picking S1 because S1 is the is is the big boy here uh in the sense that it's got six elements in it right it up on top uh and so so You' pick uh approx or heuristic algo I would pick S1 S4 S5 and S3 in that order right I won't go over it it's not that important the point is it doesn't get you the optimum for this problem and in general you could always concoct examples where any heuristic fails of course right because this problem is hard uh but it's four as opposed to three and and the big question again as always is what's the bound what's the bound if you applied this heuristic uh in and what can you show with respect to the approximation algorithm what is row N here right so that's what we have to do here in terms of what the bound is and we actually going to do an analysis here that uh is pretty straightforward it's got a little bit of algebra in it uh but if you go look at that this is covered in clrs the textbook but the analysis in there uses harmonic numbers and uh is substantially more more complicated uh for uh in my mind no reason uh and so we have a simpler analysis here that is simply going to be a matter of counting um we are picking the maximum number of uh uh of elements every time the best we can do it's a greedy heuristic we're trying to uh shrink our problem uh as much as possible initially we have X and then we're going to get a new problem let's call it x0 first for the initial problem we're going to get a new problem X1 and we're maximally shrinking uh uh X1 in relation to x0 in the sense that we're going to remove as many elements as we can because that is precisely our heuristic so the the big question is as we go from the bigger biggest problem that we have the original problem to smaller and smaller problems when do we end up with nothing when we end up with nothing that's when the number of iterations that corresponds to the number of Si that we picked is going to be the collection of Si in our solution and the cardinality of that is our cost right so that's that's all pretty straightforward uh hopefully so but what we need to do of course is is show a proof and the way we're going to do this is by a fairly straightforward counting argument assume there's a cover SE opt such that copt equals t Okay so the cardinality of copt equals T so I'm just assuming that this T subsets in my Optimum cover okay T sub sets in my Optimum cover now let X of K be the set of elements in iteration K and let's assume that x0 equals x so initially I'm at zero and I want to subscript this because I want to point to each of the problems that I'm going to have as I shrink this uh set down to nothing right now I know that for all K including of course x0 XK can be covered by T sets Okay I mean that's a kind of a vacuous statement because I assumed that x0 could be covered by T sets and x0 is only shrinking to X1 to X2 2 Etc and I'm just saying all of these things could be covered uh each of those uh intermediate problems as well can be covered by T in fact in the solution that we have in the optimal solution um it if if this these X zeros are coming from my heuristic but if they were coming from an Optimum solution uh then uh uh x0 would be covered by T X1 would be covered by T minus one and T minus 2 and so on and so forth but I I don't have an Optimum algorithm here I just have my heuristic algorithm and I'm just making a fairly vacuous statement as I said based on my definition that the original problem can be covered using T and therefore a smaller problem where I removed elements from it could also be covered using T okay so far so good um so now one of them covers what what can I say about one of them what what principle can I use to to make a claim about the number of elements that are covered by one of these T sets remember a a principle from way back 6042 my favorite principle flopping I think flapping pigon hole pigon hole principle right right see you have to remember all of the material that you learned in MIT for the rest of your life okay you never know when it's going to be useful okay so here you go pigeon hole my favorite principle uh it's such a trivial principle but um so one of them covers at least XK / T I mean why is this even a principle right elements okay so that's it right that's the observation uh and now that implies that an algorithm because it's going to pick the maximum of these right the algorithm is going to pick the maximum of these so uh it's going to pick a set of current size greater than or equal to XK / T um otherwise the algorithm would be incorrect it's not doing what you told it to do right it's got to pick the maximum so keep chugging here and one real observation and then the rest of it is algebra so what I can say is that for all K XK + 1 which is shrinking is less than or equal to 1 - 1 /t XK okay that's the way I'm shrinking right this is again a fairly conservative statement because the fact of the matter is that I'm putting T in as a constant here right but T is actually in effect changing obviously way through the algorithm I don't need uh T sets to cover the X uh whatever it is XK over2 or whatever it is that I have right I need the T for x0 maybe uh I did a bad selection with my heuristic and I still need I still would need T which is Optimum remember for X1 but halfway through the algorithm after I picked a bunch of sets I'm still saying I need t Okay because I just need that for my proof right that's all I need for the proof in clrs this actually varies and and it turns into a harmonic series if we won't go there okay you can do the uh natural logarithm of n + one appr proof just doing this simpler analysis okay so you see what's happening here that's my shrinkage that's the recurrence if you will that tells me how my problem size is shrinking and when do I end what is my stopping point what's my stopping point mathematically when do we end this lecture when you give me the answer no not quite so I end when I got nothing to cover right so when one of these things is uh gets down to XK equal Z right when XK equals z I'm done I'm constantly taking stuff away when XK equals zero I'm going to be done okay and I I I'm going to move a little bit between discrete and continuous here it's it's all going to be fine but what uh I I have is if I just take that I can turn this this is a recurrence I want to turn that into a a series so I can say something like 1 - 1 / T raised to K * n and this is the cardinality of X which is the cardinality of x0 right so that's what I have up there and that's essentially what happens I constantly shrink as I go along and I have a constant rate of shrinkage here right which is the conservative part of it so keep that in mind but doesn't matter from an analysis standpoint okay so if you look at that and you say what happens here well I can just say that this is less than or equal to e raed to minus you knew you were going to get an e because you saw a natural logarithm here right um and so that's what we got and uh basically uh that's it uh you can uh you can do a little bit of algebra I'll just write this out for you but I won't really explain it uh you're going to have XK equals z you're done the cost of course is K right the cost is K because you've selected k subsets right that's your cost right so when it gets to the point you're done and the cost is K so what you need is um you need to say that e ra to minus KT / n is strictly less than one because that is effectively um when you have strictly less than one element it's discrete so that means you have zero elements left to cover that means you're done okay so so that's your condition for stopping so this means that eus KT * n is less strictly less than one and if you go do that uh you can you get k/ T um greater than just about greater than natural logarithm of m n the algorithm terminates if we just do a little manipulation and that implies that k / T less than or equal to natural logarithm of n + 1 um is valid right k/ T is is going to be less than or equal to Natural logorithm of n plus one because if the instant it becomes greater the algorithm terminates all right and that's how you got your proof over here because this is exactly what we want K is our C from way back where it's the cost of our heuristic or cost of our approximation T is the optimum cost um that's what I defined it as and this is a bound on k/t all right cool any questions on this okay so this approximation ratio gets worse for larger problems just like this other approximation uh algorithm that we didn't actually prove from the very first problem that also got worse um it was uh it was the we had a log K factor for that and as your problem size increased obviously the approximation Factor increased inreased this is a little clearer um as to um as to what the increase looks like in relation to the original size of of n right so it's just natural logorithm of n plus one um so so far we've done approximation algorithms couple of different varieties we had a constant Factor one and then we had a a row of n that actually had a dependence on N um now let's move and we'll do one last example um on partition which um it turns out has a trivial constant Factor approximation scheme uh and it's this this obvious thing and we'll get to that in just a second uh but what is uh nice about partition is you can actually get a ptas right polinomial time approximation scheme and FP Tas fully polinomial time approximation scheme uh that uh uh essentially give you uh with higher and higher run times uh they're going to give you solutions that are closer and closer to Optimal right we want to do the FP Tas we'll do the P Tas right so partition is is a a trivial little problem to Define it's just you have a set and you want to partition it into two sets uh such that they're not unbalanced so your your cost is the imbalance uh between the two sets and you want to minimize that cost you'd love to have two sets that are exactly the same weight but if one of them is extremely uh unbalanced with respect to the other then you it's bad either way uh so so here we go with Partition sets of n items with weights S1 through SN assume S1 greater than S2 SN I without loss of generality so this is just an ordering thing I mean obviously there's some order I'm not even claiming uniqueness here I'm just saying just assume that this is the order the analysis is much better if you do this if you make this assumption and I want to partition into a and B to minimize Max of Sigma I belongs to a SI Sigma I belongs to B SI and this is the weight of a and this is the weight of B and so um there's only so much you can do um if you if you have 2 L equals Sigma I = 1 through n SI I uh so I'm just calling that to L the the the sum of all the weights then uh my Optimum solution uh is what it's a what is the lower Bond on the optimum solution if uh if it's 2 L what's the trivial lower Bond just L right so I could have L here and L there and if I had 2 L here and zero here uh then oh that's right yeah I want to minimize remember don't uh I maybe that's what threw you off it threw me off right here I see a Max here and and I got a little worried but uh I want to minimize the maximum of these two quantities okay and so um the best I could do is to keep them equal and if I get L for both of them that would minimize the maximum of the those two quantities if I had 2 L and zero then the maximum of those two quantities is 2 L and obviously I haven't done any minimization so now you see why there's a trivial Optimum solution is greater than or equal to l right and and now you see why there's a trivial two approximation algorithm uh because the worst I could do is 2 L right I could dump all of them on one side constant time and the other one is zero and my my cost is 2 L so I'm within a factor two in this problem trivially so unfortunately that's not the end of the lecture okay so we got to do better I mean clearly there's more here you'd like to get much closer this is a different kind of problem and it'd be wonderful if you could get with an Epsilon right I'm within 1% how long does it take me I'm within 0 1% guaranteed how long does it take me right that's what an approximation scheme is as opposed to just a plain algorithm so we're going to actually talk about um Eep Epsilon uh here and we're just doing a p test so we're going to see something that U is not polinomial in 1 / Epsilon it's polinomial in N but not polinomial in 1 / Epsilon but there is an fpts for this problem that uh you're not responsible for so this is going to be an interesting algorithm simply because uh we now have to do something with Epsilon it's going to have an extra input it's not going to be this simple juristic where I'm going to do maximum degree or maximum number of elements or anything like that right I want to take this Epsilon and actually do something with it right so how does this work well basically what happens in ptases or in a bunch of them is that you essentially do an exponential amount of work uh given a particular Epsilon to get a partial optimal solution so you can think of um you can think of Epsilon as essentially being one 1 divided m + one where m is some quantity and um as M grows uh the complexity of your algorithm is going to grow but obviously as M grows you're getting a Tighter and Tighter Epsilon you're getting guaranteed closer and closer to your Optimum right and so we're going to have two phases here in this particular approximation scheme uh the first phase is find an optimal partition a prime B Prime of S1 through S and uh we're just going to assume that it's exhaustive search which looks at all possible subsets and picks the best one okay and how many subsets are there for a a set of size M it's 2 raised to M so this is going to be an exponential order 2 raised to M algorithm okay I'm just going to find the optimum partition through exhaustive search for M right m is uh less than n right so I'm picking something that's a smaller problem I'm going to seed this so the way the scheme works is I'm seeding my actual algorithm my actualistic with uh an initial partial solution and uh depending on how much work I do to create the seed I'm going to end up having higher complexity and obviously that's a function of U small M right or 1/ Epsilon um and so this takes uh this optimal T takes order 2 ra to M time and you can think of that as um order 2 ra to 1/ Epsilon and so that's why it's a ptas and not an fpas okay so this is ptas what else do we need to do well I don't actually have a solution yet because if m is really small and and by the way M can be zero as well right uh Epsilon would then be a two approximation one divided by uh this would be 1 half and so 1/ Epsilon is two so then you got your trivial algorithm that we had the two approximation scheme right so that makes sense so the second phase is uh you're going to start with your seed corresponding to uh A and B uh you're going to set them to a prime and B Prime and what I'm going to do is for i = m + 1 to n if w a less than or equal to WB a equal a union I uh running out of the room else uh b equals B Union I okay so uh it's not that hard to see hopefully um all I'm doing here is I'm just going in a very greedy way I got my uh my initial a prime and B Prime I set them to A and B and I say oh I got this element here which one is bigger oh this one is bigger I'm going to put the element over here and then I look at it again got another element which one is bigger and I go this way that way that's that's pretty much it right so again all of these algorithms are really straightforward uh the the interesting part the fun Parts in showing the approximation guarantee so we good here yep all right so uh back to analysis one last time so let's see um we want to show that approx partition ah you know how to spell partition is P I guess I don't but you do uh let's assume that w a is greater than or equal to WB uh to to end with right so I'm just saying at the end here I'm just marking the one that was larger that came out of the max as a right without loss of generality just to make things easier I don't want to keep interchanging things so our approximation ratio is W divided by L right wa could at best be L if if I got a perfect partition perfectly balanced but it could be a little bit more and that's my approximation ratio okay so I I need to now figure out how the approximation ratio reflects on the runtime and is related to M and therefore Epsilon all right so what I'm going to do here is I'm going to look at a point in time where I have a and b and remember that W is defined to be greater than WB but here I'm looking at some point in time which is not necessarily at the um at the very end here it it could be but you can think of this as being I'm just going to say b or um intermediate B and this won't matter too much but I'm just being a little uh bit uh of a stickler here but I'll explain why I said that in just a minute but the point is I have a a situation where I know that the wa is greater than WB or greater than or equal to WB because I assumed it that's how I marked it and I'm I'm going to look at K is the last element added to a is it's is being added now this could have been added in the first phase or the second phase it's quite possible that for a given M that if it's large for example that the a that you you the a prime that you end up with uh is your a to begin with here and that you never execute uh this statement okay it's quite possible right um you you you got your uh initial seed and you never added to it and that was it because your M was large for example right so what I'm saying here is K is the last element added to a okay so there's clearly a last element I'm just marking that um and we know that a is greater than or equal to B now it may be true that if I'm looking at the snapshot when just after I add the K element to a I may not quite I may not be done yet in terms of I still have a few elements and I may be adding elements to B but regardless given my definition I know that b is less than the weight of B is less than the weight of a because even though um the last element overall may be added to B uh WB is is less than wa and I'm only looking at the last element added to added to a here okay so uh why all of this skull dugery well there's a there's a method here to the madness uh we're going to analyze what possibly happens in the first phase and the second phase and get our approximation ratio shouldn't take too long so there's two cases here that we need to analiz the first one is easy second one is a little more involved I'm going to now assume that uh K was the last element and was added in the first phase okay if K is added to a what can I say if K was added in the first phase to a and and that's the last element added throughout the algorithm by the time you get a partition what can you say what can you say about the solution what strong state M can you make about the solution what's the only interesting statement strong statement that you can make about a solution right so I I I got to a remember what the fa first phase is what's the first phase well it's optimal right so after that what happened to a well it didn't change right so what you got is Optimum right because W was defined to be greater than or equal to WB wa was Optimum for the smaller Problem whatever M was you never added anything else to it so you're done it's optimal so you're in this case your approximation ratio is one because you got the optimum solution right so if K is added to a in the first place this means AAL a prime we have an optimal partition since we can't do better than W Prime when we have n greater than M items and we know w Prime is optimal for the M items okay so so that's cool that's good so we we got an approximation ratio of of one there of uh uh and and remember that this is not taking overall exponential time necessarily it's just a case where I've picked some arbitrary M and it happens to be the case that a equals a prime at the end of the algorithm so I am taking exponential time in in M right M as in Mary but I'm not taking exponential time is is in N right n is in Nancy so the second part is where the approximation ratio comes in uh K is added to a in the second phase so here what we're going to do is we're going to say we know W A minus SK is less than or equal to WB right this is the second phase we're talking about here the only reason SK was added to a was because you decided that uh a was the side that was smaller right or perhaps equal right so that's the reason you added it into it so you know that W A minus SK is less than or equal to WB at at that time so think think of A and B here as being variables that are obviously changing right uh um but I what I'm saying here um is if you even if you look this is the algorithm where A and B you constantly look at them and decide which way to go but if you look at uh the the last step then you look at the final value then you can certainly make the statement for those final values that the wa which is the resultant value minus SK should have been less than or equal to WB uh and you had a smaller W to uh to begin with uh and you added SK to it and that happened in the in the second phase okay so this is why K was added this is why K was added to a I want to be a little careful here given that we're using we overloading A and B but I'll try and point out what each of these statements actually means and and uh ask questions if you're if you're confused um I know that w a - SK is less than or equal to 2 lus W all that's just a substitution because W A + WB equal 2 L okay and then last little trick again it's it's algebra nothing profound here um we we have our assumption that we ordered these things um so you had S1 through uh SN excuse me the whole the whole thing was ordered um and so we can say that S1 S2 all the way to S is greater than or equal to SK uh we are actually doing this in order we taking the bigger elements and then deciding where they go so we sorted those things initially and so what we end up with when we look at SK we have taken care of values prior to SK that are all greater than or equal to SK right that's uh again using our initial assumption so what that means is 2 L is greater than or equal to m + 1 SK since K is greater than M right again this is not particularly tight um because M could be really pretty small in relation to n but I do know that I can make the statement that um since the values are decreasing that 2L which is the sum of all of those is greater than or equal to m + 1 * SK regardless of what m is right uh and so so that's pretty much it uh once you do that you have your approximation uh ratio uh let's leave that up there because that's the algorithm finish this off with a little algebra all right so w a divid by L is less than or equal to l + SK / 2 / L I'm basically substituting I have this and I have that and I'm playing around with it um and I got one + SK divided by uh 1 + SK ided 2 L um which is now this I can say is equal uh that's simply equal this I have less than or equal to and then I can go less than or equal to 1 + SK divided by m + 1 SK and then I got 1 + 1 / m + 1 which is of course 1 plus Epsilon right so all I did here was use this fact and and and essentially relate two to SK and once I could relate 2 L to SK um substituting for uh SK in in in here I I I ended up with the approximation ratio that I want wa over L is L plus SK ided two that simply comes from here um and you know plug that in divided by L and then um I have uh SK divided by 2L and then this part here 2L is going to uh get substituted by m+1 SK and uh voila I'm over here okay so um the story behind this uh particular uh problem was uh it was in the quiz and Eric I guess took the quiz did you actually take the quiz or edit the quiz and he says this problem is impossible um it was a it was a it was a problem he said this problem is impossible I had to Google it to find out the answer or something like that and I said well I'm going to give the answer in lecture right so there you go so remember this write it down four points for coming to lecture today right see you guys next time