Harvard University · 1:25:04 · https://www.youtube.com/watch?v=2Gl-yNso0_0
0:02 okay so I'll get started sent an email but just in case someone didn't see it uh next week we're having two guest lectures one on Tuesday one on Thursday the Thursday one will not be recorded So if you want to see that lecture you should be here in person okay so today I want to uh wrap up with approximation algorithms so
0:28 um uh we're going to finish FP tasks this is for NP we're going to do it for napsack two um we're going to look at F presses I'm going to do this for dnf counting and then three we're going to look at uh semi-definite programming
1:08 and we'll look at Max cut and if we have time we might look at one other application as well okay so let's get started so last time we saw with napsack um that there was a ptas right a ptas just means for any fixed Epsilon you can get a 1 plus Epsilon approximation or for for napsack I guess a one minus Epsilon approximation and your running time is a polinomial in N if epsilon's a constant
1:41 but with an FP Tas we want to say that your dependence on Epsilon is also polinomial okay so so we want um poly and one over Epsilon dependence for napsack and I think actually what we'll get is today we'll just see it's a very simple algorithm it'll get you n cubed over Epsilon 1 minus Epsilon
2:18 approximation okay um do I have a scribe today good okay um the I did some searching around to see what uh the best known bound was for napsack uh so it's possible to get with a different algorithm a running time of n * log 1 Epsilon plus one or Epsilon to the 4th
2:48 this is due to a Lawler [Music] in 79 I searched around a bit to see if there was anything after 79 where someone improved this but I couldn't find things maybe I just didn't search hard enough um so yeah there you go for if you want a final project I'm I'm just
3:14 kidding um yeah okay so um good so let me show you this algorithm so this is an idea that gets used a lot in FP tases which is so the idea is rounding so remember the setup okay we have n items we have a napsack first of all a
3:45 napsack of size W capital W and then we have n items with uh weights W1 up to WN and also values V1 up to VN remember and the goal is to pack this napsack um don't don't overload it you can't put more than W total weight in the napsack and uh the items that you put in there you want you you're going to collect the sum of values of those items and you want to get as much value as
4:28 possible okay okay so the basic idea is well what do we know we know that there is an algorithm with running time NV right so we mentioned this last time this is via dynamic programming where here V is just the sum of the
4:58 vi okay and unfortunately this is not polinomial time because the running time depends on the sizes of the numbers as opposed to the logarithms of the numbers okay writing down a number V only takes log V bits so the input is exponentially smaller than V potentially
5:17 okay uh so the trick is just to make V small okay so to get FP Tas what are we going to do we're going to Define new values we're going to set V Prime to equal or VI Prime to be n over Epsilon
5:47 times uh VI over V Max and let's make it let's floor it so that it's an integer okay and then run an O of n v Prime algorithm that's going to give us a set right this is going to be an exact algorithm for the new
6:16 values okay and that's going to give us a set of items which is the optimal thing for this new set of values and the claim is just if you use that set for the original problem with the original values you'll get at least 1us Epsilon times opt okay so I'll justify that for you but what's v Prime
6:41 here or any bound on V Prime capital V Prime n squ over Epsilon right so this thing this thing here we have V Prime is at most uh n * the max over I of V I Prime and well VI is at most Vmax certainly so this is at most one so this is at most n over Epsilon so this is at most n Square over Epsilon so this running time is at most what I said n Cub over Epsilon so that's all there is to
7:20 it and the the basic idea is something fairly simple so what's the basic idea okay first of all we know that opt Prime by opt Prime I mean op the value of opt in the new problem okay after you change these values opt Prime is at least Vmax
7:47 Prime right the maximum value um the maximum value of the vi primes right and one of the items actually has V Max right so that item will have at least n over Epsilon value okay but how much value did we lose uh in any given
8:17 solution in this new rounded problem well for each item in a set we rounded down its value after this multiplication right so by rounding down we at most decreased its value by one so I mean the basic idea is I'll make this more
8:36 formal after rounding right I mean if there was no rounding if we just if we just multiplied by some scalar on every single value then op doesn't change right every set just has a the same multiplicative uh Factor times its old value but by this rounding we potentially lose one from every value so after rounding
9:00 any set let's call it s a subset of the items loses at most s which is at most n value right which is at most Epsilon time Ops Prime okay so let's just now make this a little more very slightly more formal so
9:34 claim if DP unrounded instance returns some set a okay which is subset of n then the value of a is at least one minus Epsilon opt the original if you take the uh the original valuation and compare to opt of the original problem so
10:13 proof okay what's the proof of that well for all sets s what we said over there s subset of one to n we know that the value if you look at so so um let me write it like this so Alpha so the value Prime of s is at least Alpha the old value of s minus the size of s and it's at most Alpha times the value of
10:48 s where Alpha is this scaling that we're doing um and over Epsilon time VMAX right that's what I just said over here we lose at most the size value so let a star be some optimal set for the original lapet problem before rounding
11:34 right so what do I want to show I want to show a lower bound on the value of a what do I know well I know that the value of a is at least one over Alpha times the value Prime of
11:51 a right that's just that inequality here and then I know that a is the optimal solution to the new valuations right so this is certainly at least 1 Alp time V Prime of a star okay and now now I want to go back toward opt for the original problem so V Prime of a star this is true for all sets so in particular it's true for a star V Prime of a star is at least Alpha V of a star which is opt minus the size of a star so this is at least
12:32 uh Alpha times so this is V of a star which is opt this is opt minus Alpha times uh or one over Alpha sorry times the size of a star okay [Music] um and that's certainly at most n so this is at least opt minus n over
13:14 Alpha which is equal to which is at least opt minus Epsilon time V Max that's just the definition of alpha right and now VMAX opt is opt is certainly at least V Max okay so that's that's it so are there questions
13:46 about about this FP task okay there are no questions then let's be done with napsack and before I move actually before I move on to fesses you know you could ask when can I know for sure that there is no FP
14:25 task right not every problem has an FP task okay okay so uh for example for set cover we know you can't beat login approximation not just because of integrality gaps but there's actually a proof that unless you can solve sat really fast which we don't expect there's no there's nothing better than a lawn and approximation sometimes for some problems you know you can't beat a two approximation for vertex cover it's known that there's a fixed constant um I forgot exactly what that constant is but it's bigger than one
14:54 that unless P equals NP you can't beat that approximation ratio okay and there's there's also some recent more recent evidence that says you can't beat a two approximation if you assume some conjecture but okay but sometimes there are just kind of easy reasons why there's no FP Tas okay
15:14 so you don't always have enough P tests and let's give it a very simple example so bin packing okay in bin packing what's the input they're n items with sizes S1 S2 up to SN and all those sizes are in the range from 0 to one
16:01 bins have capacity exactly one and then the the goal is to pack all items into as few bins as possible okay and you can't cut items up okay so either you have to put an item fully into a single
16:44 bin people have questions about the problem statement okay so it's known that bin packing as I've stated it here is NP hard okay and the decision problem the decision problem of can can you pack these bin these items into even two bins that even that problem is NP complete
17:12 okay so question given what I've just told you do you expect to have an FP task for bin packing right you should use at most one plus Epsilon times the optimal number of bins so what would an FP Tas for bin packing mean
17:50 okay so an FP task and your runtime to find this packing is polinomial In N as well as one over Epsilon right do you expect to have an FP task for bin packing why not okay that uses fewer than but but why can't you
18:32 yeah yeah right so the point is so the reason so we don't have an FP Tas unless P equals NP what's the proof of that if we had FP Tas run it with Epsilon much less than you know 1 over n or something then the point is the error in the number of bins you use will be less than one and we know the number of bins you use as an integer okay so if I tell you there is a packing us using at most 2.2 bins well then you know that there's a packing using two bins right so um you can you could have solved that decision problem with an FP Tas and it would have been a polinomial time
19:22 algorithm okay so you don't always expect to have an FP Tas and uh I guess the term that's used when you don't have an FP task is that the problem is strongly NP hard okay um good so that's all I want to say now about FP
19:50 tases and I want to move to fasses okay so F press so two F press it's like an FP Tas but you know the algorithm is randomized and has you know some onethird chance of failing to find a good solution
20:33 at most a one3 chance so I want to give you an example for this as well okay which is dnf counting okay so maybe people remember what cnfs are um from threat or sat right so cnfs are formulas written so it's called conjunctive normal form dnfs d d stands for a disjunctive normal form what does it mean it means that you have some Clause so an input what does an input look
21:16 like it looks like a clause I'll say what a clause is in a second a clause C1 or C2 or dot do dot or cm and a clause some CI looks like some X you know J1 and xj2 and whatever and X Jr and some of these might be negated you
21:54 know and right the satisfiability problem for dnfs is um right in cnfs you sort of flip where the ANS and the ores are right so in a CNF you would and a bunch of Clauses and each Clause would be an or of some number of
22:10 literals okay in dnf you chain you reverse that and we know from you know we know from the cook L theorem that sat is an NP complete problem okay so sat at least is NP hard how about the decision problem I mean the decision problem for sat is if you're given a CNF formula does there exist an assignment to the variables
22:40 which causes the formula to evaluate to True how about for dnfs if I give you a dnf and I ask you is there assignment is there an assignment to the variables which makes this thing true right is that hard no why is that not hard
22:56 well you solve any Clause so this thing is satisfiable if and only if at least one of the Clauses is satisfiable and then you can just go Loop through Clause by clause and just check that you know basically it's satisfiable as long as you don't have X and not X somewhere
23:15 right okay so dnf satisfiability that that problem is in P there's a polinomial Time algorithm for that it's a pretty simple algorithm how about dnf counting given a dnf given a dnf formula count the number of satisfying of satisfying assignments to the V to the
24:05 variables okay do you expect that to be easy any thoughts that all yeah yeah exactly so if you could count a number of dnf solutions you could solve sat right because if you have so this is a hard problem to do it
24:50 exactly so the proof that it's hard is that if you have a SAT formula let's say you have you know X1 uh and not X2 and X4 or something uh whoops this is this is a dnf let's say if a set formula looks like that and you have some other thing
25:13 X5 or not X1 or whatever right so you want to know you want to know whether or not this thing is satisfiable this is your in this is your input for sat well if you could count the number of solutions and tell how then then you would know whether or not it's satisfiable because you would know whether the number of solutions is zero or not right so how could you count the number of solutions to this CNF
25:38 formula well you could negate it just negate the whole thing right and then this just become the negation of a CNF is a dnf right so notice that C1 or C1 and C2 negation is just equal to negation of C1 or uh negation of
26:04 C2 right so if you have a CNF so here if you have a CNF CNF this is now a dnf and you know you could have you could have lots of Clauses here and if there are n variables well if the number of solutions to this dnf is
26:31 T then that means the number of solutions to the negated CNF is T which means the number of solutions to the non- negated CNF is 2 the N minus t right so if you could count the uh solutions to the negative then you got you you're counting the solutions to the original
26:49 thing does that make sense Okay so solving the counting the exact counting problem for dnfs is NP hard in fact it's even harder than NP hard it's what's called sharp P hard okay so in fact there's I'm not going to dwell much on this in fact there's a complexity
27:20 class sharp p and a complete the complete problem for Sharp p is counting the number of solutions to sat okay and and dnf Counting happens to be complete for that class dnf counting is sharp P complete sharp is like number so it's like counting yeah I mean that's where that name came
27:55 from but it's it's a class that contains NP so it's basically so for people who have taken some complexity course and have seen the formal definition of NP right in NP um NP is the class of problems where there's a witness that's verifiable in polinomial time and sharp P um in sharp P you want to count the number of witnesses basically
28:21 so it's an even harder problem than finding a witness okay so this is a pretty hard problem but you could ask ourselves well can we count number of solutions to dnf up to 1 plus Epsilon so I'm not going to get the exact number of solutions to dnf to the dnf counting problem but I'll get it up to I'll get some number that's at least 1us Epsilon times the true number and it's at most 1 plus Epsilon times the true
29:02 number okay notice that it's not immediately clear that we can't do this right the proof that counting dnf was hard really relied on the exact count right right we said that basically if we could tell whether the number of solutions to the CNF is zero or not then we would have solved
29:28 but if there's some multiplicative error here then we can't distinguish Zero from nonzero okay so and the answer the answer to this question is yes we can there's an Fess uh due to carp Luby and Madras what year is that of pross uh let me J
30:14 89 okay that's what I'm going to show you you mean a um a deterministic counting um yeah I should know I I don't think so but let me let me look into that oh um like for like is it hard for some complex would it imply collapses of complexity classes if that happened um I don't I don't know off the top of my head I I'll have to I'll look into that I'm not sure yeah is
30:51 sols other problem we haveg small yeah integer that's our answer right yeah okay so that's a good question I mean you could ask the same question for napsack right so in napsack let's say that the values the values are integers
31:09 um and the weights are also integers uh but we have an FP task so why is that right we we know that the answer for napsack has to be an integer if the values are integers right so why why does anyone have an answer why why why can we have an FP task for napsack
31:34 so let's say that let's say that the max weight let's say the max value of any item is Vmax we know that opt is certainly not bigger than n times Vmax right so what I'll do is I'll set Epsilon to be much smaller than 1 over n * Vmax I'll run my FP task it'll give me some number with with fractional error and I'll just round it to an integer because I know the answer has to be an integer right so what's
32:03 sorry it's not polinomial why right yeah so right exactly so it's that same issue right so with napsack the problem is that you don't want to run in time proportional to the numbers you want to run in time proportional to the description of the input and to write down Vmax takes log Vmax bits so you would have to set Epsilon to be too small and po1 over Epsilon wouldn't cut it okay and it's the same with dnf counting it's a similar thing you can have dnfs where the dnf has size n or something but the number of solutions to that dnf is exponential in N right so imagine a
32:42 dnf which is uh X1 or X2 or X3 Etc it has exponentially many solutions right the only thing that's not a solution is if all the X's are false so it has it has 2 to the n minus n Solutions um so if you wanted to get that answer accurately You' have to set Epsilon to be one over that and then poly one of epson would be exponentially
33:09 big okay so so the idea behind um you know the way that we're going to get started developing this carp Luby Madras algorithm would be to you know to try out the first thing that might come to mind if I tell you come up with a randomized algorithm right uh but there's going to be a problem and then we're going to have to be we're going to have to use a clever trick to get around that problem
33:36 so what's one way to um randomly estimate the fraction of so there are there are two to the end assignments let's say there are n variables and N clauses sum of the 2 to the N variable assignments satisfy our formula our dnf
34:20 formula let's say let's say a p fraction right so really what we want to do is we want to estimate P right so are are people with me okay so how would you estimate P yes sample a random assignment a uniformly random assignment check whether or not it satisfies your dnf and do this a bunch of times and take the empirical mean right or take see what empirical fraction satisfies uh your
35:02 dnf okay so what's wrong with this algorithm onlys yeah right if there if p is very small in fact if p is one over two to the N so there's only one assignment you're not going to see a satisfying assignment
35:24 unless you sample exponentially many assignments right so so a bad example for this is you know what if the first what if the Clause whatever your dnf formula is just um X1 and X2 and dot dot dot and
35:46 xn okay there's only one assignment and you're not going to see it you're going to think the answer is zero unless you do exponentially many U samples so really the problem is that P can be small so the trick in this F press that I'm about to show you is to rig
36:10 things so that P is not too small okay so here's the let me let me just call this a KLM so okay so what what does KLM do okay let SI be the set of assignments satisfying satisfying Clause
36:54 ey and now set u to be uh well not you let's say B set B to be the union over all I from 1 to M of Si we want to estimate the size of B up to one plus Epsilon okay now define B Prime
37:33 to be um how should I put this the set of all pairs I comma X such that assignment X satisfies uh Clause ey or if you want to think about it uh I don't know I wanted to write it explicitly so you know what I'm saying I think some people use this notation the disjoint Union of
38:25 Si Okay so each each assign each satisfying assignment is not written just once in the set it's written multiple times once for every Clause that it actually satisfies okay okay so notice that so question we want to estimate the size of B is it is it easy or hard to estimate the size of B Prime
39:31 um wait in in this right I mean in general I give you a dnf right I give you an arbitrary dnf which is an or of a bunch of Clauses a clause is just an and of some literals and I want you to I want you to compute or estimate the size of B
39:50 Prime okay you don't have to be shy you know just yell it out I see a nod okay so explain your nod right yeah so the point is um the size of B Prime is the sum of the size of Si where I goes from 1 to M and what's the size of Si
40:22 well this is just 2 to the N minus um number of literals in C right so for the literals that actually appeared in the I Clause you know what you have to set them to to make this and evaluate to true and then all the other n variables you can just set to whatever you want or all the other n minus number of variables you can set to whatever you want okay so the point is we can actually compute the size of Prime
40:57 exactly uh very quickly so now instead of estimating this P let's estimate P Prime which is the size of B over the size of B Prime and then once we get that once we get this we'll just multiply it by the size of B Prime which we know and then we'll get the size of B up to some error
41:27 okay so what's a lower bound on P Prime the problem before was that P Prime could be too small right so now it's a lower bound on P Prime can can p Prime be too small one over M right so P Prime note P Prime
41:57 is at least 1/ M right because each assignment in B appears at least once in B Prime and it appears with multiplicity at most M right so B Prime is at most an M Factor larger than b is okay so P Prime is not too
42:19 small and now how can I give me an algorithm to estimate P Prime for right so what we want to do is we want to pick somehow do something similar what we did before which didn't work pick a random assignment and then reject and then you know reject it if it's not in b
43:28 the problem is that a totally random assignment is probably not in b or it might not you know the chance that it's in B is really small so instead what do we do right we need to pick a random element of B
43:47 Prime and check if if a random element of B Prime is in B right so right so pick a random element of B Prime and check if it's in B well checking if it's in B is sort of a weird thing to say because kind of the types of the elements of B Prime and the types of of elements in B when I say type I mean in like in programming languages right like
44:27 an element of B is a bit string of length n right it's a true false assignment an element of B Prime is not a bit string of length n it's a bit string of length n together with an index from 1 to M so what is you know what do I mean when I say check if if the element of B Prime if this pair check if it's in B right so what's one
44:52 way how how can I implement this check if it's in B and then we'll also talk about picking a random element but how can I check if it's in B yeah oh um so the way a dnf is to satisfy the entire thing you just have to satisfy one of the Clauses right so any any X in B Prime definitely is in this
45:19 set right so I want to basically what I want right what do I want I want a bje between B and a subset of B Prime so that it makes sense to check that this element of B Prime is in B okay and I'll just spill oh yeah yeah so check so look at so what's the bje going to be basically for every assignment X that appears anywhere in B
45:45 Prime its representative which corresponds to it being in B will be the I such that it's the first time I is the the index of the first Clause that X satisfies okay so bctiv map B into the set
46:14 iix so B Prime uh well this is bad notation where CI is the first clause X satisfies right so each satisfying assignment is counted exactly once now and we can check that right once we get an element of B Prime we can just now take that X compare like run it through every clause and make sure that that I is the first time it satisfied so we can check that
46:46 quickly okay how about picking a random element of B Prime how do we do that how do pick a random l in a V Prime how do I choose a clause CL choose any Clause okay okay you mean not randomly just
47:33 arbitrarily randomly okay uniform like under what distribution uniform okay we so we could do that I don't know I don't know how to make a uniform Clause work but okay you have a suggestion yeah um wait so okay so I think so yeah so you said we'll pick Clauses prop like that with probability dependent SI of
48:25 the SI of the size of the Clause okay so not yeah not quite the size the size of Si right right okay good so the point is what are we going to do we'll first pick a clause I pick a clause
48:47 randomly where the distribution is as follows Clause I is picked with probability the number of assignments it has over the sum J from 1 to M of size of SJ right so not uniformly but according to this distribution right and then
49:14 now then pick a random satisfying assignment for CI a uniformly random assignment uniformly okay right so if you pick from B Prime this way then um you will guarantee that the element you get is a uniform a uniformly random element from B Prime now we already said we know how to compute these things right so we can actually do this the size of Si is just well we wrote it somewhere before two to something minus something maybe I erased it
50:13 already top oh yeah there the size of Si is that two to two to n minus number of literals in CI so we can compute this we can compute these numbers yeah so if you ever have a clause if you ever if you ever a clause that's ever like X and not X then you can just throw that out of your dnf because there's no way you're ever going to satisfy
50:35 that okay um and now picking a random satisfying assignment well how do you do that for the Clause well the variable the literals that are actually in the Clause you set them to what they have to be and everybody else you just pick uniformly at random
50:52 okay so that's that okay so that's the entire algorithm that's gonna um we sample and estimate P Prime so now we just want to argue that this works so that the total the final algorithm is uh sample T
51:20 elements from uh B Prime uh let P prime or let uh P Prime Tilda be fraction of T sampled elements that are actually in B and then three will output P Prime Tilda times the size of B Prime are there questions about what the algorithm
52:16 is so does anyone have any ideas for how we might prove that this algorithm works well okay well I saw it on people's lips but no one wants to speak it loudly so the turnoff bound right so analysis turnoff
52:46 bound right so more formally let X1 up to XT be such that XJ is one if the J sampled element is in B and zero otherwise um and let X be the sum from Jal 1 to T of
53:24 XJ so what's the expectation of X well by linear expectation it's going to be P Prime * T so now when does this algorithm fail this algorithm fails if this if x minus its expectation is bigger than Epsilon times the expectation
54:00 right so this is this this means we failed we failed to get a good approximation so what's the probability of that well the turnoff bound says that it's at most uh well the turn of bound says 2 * e to the minus Epsilon 2 mu mu is the expectation uh over some constant I don't know three or four or
54:36 something and what's this thing we said this thing is p Prime T right so this is less than Delta if T is at least some constant times um log one over Delta over P Prime * Epsilon s right and remember we know that P Prime is at least one/
55:18 M right that was the problem before we could have done the same exact argument in the beginning where we just sampled random assignments and saw what fraction of them worked the problem then is that P could have been 2 to the N or something which means we need at least 2 to the N samples but the point here is that P Prime is not too small P Prime is like 1/ M so this is
55:42 just m * log 1/ Delta over Epsilon s okay so we take a polinomial number of samples um for each of the samples in Pol time we can check whether or not it's in B we can do the sampling in polom time so this is all a polom Time
56:03 algorithm so that's that's it that's an F press for dnf counting okay questions about I'm gonna I'm going to move away now from F prases and FP tases and move to another topic another approximation algorithms topic so before we do a switch are there any questions
56:53 so I haven't told you yet how algorithms work to actually solve linear programs I just claimed that there are algorithms to do it um after so next week you're going to see some guest lectures when I come back we'll start talking about how to actually solve linear programs so now that we're in the phase where um I'm just claiming certain things can be solved without actually proving it I'm going to claim that we can also solve semi-definite programs okay so uh I should first Define what what that
57:22 is so semi-definite programming I'll just just like linear programming is often called LP this is usually called sdp um so what is a semi-definite program what okay good so so stdp so x capital x is an N byn
58:01 Matrix so linear programming we're trying to solve for some Vector X now we're trying to solve for some Matrix X and what the problems look like are minimize the trace of cpose X I'll say a sec second how to interpret
58:22 this such that for I from 1 to m the trace of AI transpose X is equal to bi okay so just like LP LP is you minimize c.x subject to AI dox is bi for a bunch of different rows of this Matrix
58:47 a but now both a and X Ai and X are both matrices now and there's also these non- negativity constraints okay and we're going to replace the non- negativity constraints with uh well it's called semidefinite programming a positive semidefinite constraint um
59:07 so and and I'll say what that means I'll do a little linear algebra review X is positive semidefinite and I'll usually write this as X is at least zero with little squiggly greater than sign so known so you can see a book there's a book on semi-definite
59:48 programming what's it called again so it's called uh it's called semi-definite programming uh it's by uh Vandenberg and Boyd okay that can solve sdp up to say l bits of precision in time poly nml okay so we're just going to take that as a blackbox just like for LP I said there are algorithms out there that can solve programs in polinomial
1:00:58 time I'm just going to take for black as a black box that we can do this for sdp okay and so what is this trace of cpose X business so you can prove to yourself so I'm not going to prove it so just fact you can go and I mean it's just a computation the trace of a transpose B in general is just the sum over i j of AIG J B
1:01:34 J okay so really what this is saying is don't view X as a matrix so except for the last part which is really something Matrix specific don't view X as a matrix just view it as an N Square dimensional vector and this is really just linear programming right so this is C transpose X where C is also an N Square dimensional vector this is AI dox where AI is an N Square dimensional vector and then you have this funny constraint at the end where instead of saying that it's a non- negative Vector you say that if you view this n squ dimensional Vector as an N byn Matrix that Matrix should be
1:02:10 PSD okay so that's the difference between sdp and LP um now so what does it mean to be positive semi-definite so definition X is PSD positive semidefinite if for all vectors uh Z or let's say Y in RN we have the inequality that y transpose
1:02:48 x y is at least zero actually let me just write one more thing which we're always going to use it's going to be a is a symmetric Matrix okay so claim I just want to do a little bit of linear algebra
1:03:53 review The Following are equivalent for symmetric n byn matrices X so one or let's say a x is PSD B so remember so another fact from linear algebra is if you have a symmetric real Matrix then uh it can be diagonalized and it has a full set of real igen values this is the spectral theorem okay so B all igen [Music]
1:04:42 values of X are non negative and C um can write we can write X as M transpose M for some real Matrix M Okay so um if these things don't look familiar to you then for lecture just take them as truth and you can find them in any pretty much any linear algebra book okay I mean it basically follow so look up spectral theorem okay and you'll see all of
1:05:47 this okay so first of all first of all I claim that linear programming is really just a special case of semi-definite programming okay so I don't want to go through the details because I want to actually talk about you know for for our purposes in this lecture and what remains of this lecture I just want to say that there's this thing called sdp
1:06:12 which can be solved efficiently and now we can use it for approximation algorithms okay so I don't want to get too much into the theory of how to solve them Etc but I want to do I want to say just a couple things about them so
1:06:26 LP linear programming is a special case of sdp does anyone see why so suppose I suppose I have an LP that looks like this any LP by the way can be written in this form minimize C transpose X subject to axal B and X is at least zero in every coordinate I claim that this can be represented as an sdp
1:06:58 right yeah so exactly so so sdp okay we're going to have we're going to Define c to just be a diagonal matrix C1 CN on the diagonal okay we're also going to define AI as being a uh ai1 a
1:07:25 a i n a diagonal matrix and then we're also going to enforce we'll also add constraints to force XI J equals zero for I not equal to J you can add more constraints to force that okay and to say that it's PSD now say x is PSD well it's a diagonal matrix so all the igen values have to be non- negative which means all the entries on the diagonal have to be non- negative okay so LP is just a special case of
1:08:07 sdp and I won't say much more about this but sdp also sdp is actually a special case of LP well where you have infinitely many constraints so basically for every y you can write a constraint where you can write a constraint where the
1:08:26 race of your Matrix now is like y y transpose time x um should be at least zero okay so you have if you have infinitely many constraints in your LP you can represent an sdp but of course uh that's a really big LP
1:09:08 so now I just want to say that sdp is now really the same because of this claim sdp is really the same as VP which is Vector programming what do I mean by that we said that if x is PSD it's the same thing as saying it's m transpose M
1:09:35 which is saying it's so right it's it's a gr Matrix what's called a gram matrix it's V1 up to VN times V1 VN which means that if we look at the IJ thry of X that's just equal to V i.
1:09:59 VJ okay so this implies for example you know the trace of C transpose X that's just the sum overall i j of C jv. VJ and similarly for the other constraints that you have you can write it as just a sum of you know AI J time vi.
1:10:24 VJ right so Vector programming is well it's like linear programming except variables are do products like this so sdb can sdb can be solved efficiently so VP can be solved efficiently right and there's no there's no more once you're solving Vector programming there's no more PSD constraint because I mean you're already encoding that in the fact that you're using vectors in the first place that using these Vector dot products so VP says minimize sum over i j c vi.
1:11:13 VJ such that um for I let's say for I going from one up to M or let's say for K going from one up to M the sum over i j of AK IJ vi. VJ should equal BK that's what Vector programming looks
1:11:46 like okay so now I want to look at an example of using Vector programming which is the same thing as semi-definite programming to get an approximation algorithm so an example is Max cut okay so the input is a
1:12:16 graph gals ve it's an undirected graph and you've probably heard of mincut Max cut is Max ma imize find a cut that has the maximum number of edges Crossing it so goal find a cut a cut is just a partition of the vertices into two pieces find a
1:12:37 cut which is a partition s and V minus s maximizing maximizing number of edges going from s to the the opposite side of the partition so if you took 124 last term I think I mentioned a good approximation algorithm for Max cut uh has anyone seen any approximation algor for Max
1:13:14 cut anyone remember anything well I'll tell you just pick a random partition so for each so uh you know have a left set and a right set for each vertex put it randomly in the left and randomly in the right flip a coin probably a half it's in the left probably half it's in the right look at any Edge what's the probability that the edge crosses the partition well it's a half so in expectation half the edges
1:13:45 cross the partition and you get at least m over2 m is the number of edges so let's say this thing is is equal to M and this thing is equal to m you get at least M over two edges and opt is certainly at most M so you're getting at least opt over two edges okay um another non-random algorithm is just start with an arbitrary
1:14:09 partition and as long as there exists a Vertex that has more Neighbors in its own partition than in the other one swap it okay so this has to terminate because you're always increasing the number of edges that cross the partition and if it's now terminated then that means that every vertex has at least half its neighbors in the opposite side which means that you've you've gained at you have at least M over2 at just crossing the
1:14:36 partition okay so both of those are two approximations you get at least half of opt and for a really long time those were the best algorithms until I think it was 95 um was it 95 it was Gman and Williams yes Gman Williamson 95 well actually 95 is the journal version so it was even earlier when they wrot when they first came up with it but Gman and
1:15:07 Williamson the journal version is in 95 what did they get instead of getting at least half of opt they showed how to get uh 0.878 approximation okay and what is this number this number is the um the lowest possible
1:15:35 value over all angles in the range from uh 0 to Pi of 2 over Pi * thet over 1 - cosine Theta Okay so so that's so we're going to see that algorithm even though the number looks weird it's actually um it's actually a very simple algorithm it's just that before them people weren't using sdps to come up with approximation
1:16:10 algorithms and kind of after they did that uh it was you know it was a really influential paper so then people started saying hey maybe we could use sdps for other problems as well and in fact they did um and there's something called
1:16:25 so first of all just like LPS have integrality gaps sdps also have integrality gaps okay um so you know I'm G to write down Max cut not I'm going to write down Max cut not as an integer LP but I'm going to write it down as a quadratic program with integral
1:16:44 constraints okay and you'll see what I mean in a second we're going to relax it to an sdp by whenever we have quadratic terms like XI time XJ we're going to relax that to vi. VJ so instead of thinking of XI as being a plusus one we'll think of it as being a unit vector
1:17:03 and multiplication will be do product okay so max cut we can write it as a quadratic program we want to maximize uh the sum over edges in E where e and edges from I to J of I think 1us X x i * xj/ 2 so the point is if and here um for all I XI is in the set from minus one and
1:17:37 one okay so the point is Xi tells you whether they're on the left side or the right side of the cut vertex I now if they're both on the same side the product will be one one minus one is
1:17:49 zero if they're on opposite sides of the cut then you'll have one time * -1 which is minus one 1 -- one is 2 2 over two is 1 so this counts basically how many edges are crossing the cut this is a quadratic
1:18:04 program so by the way Max cut is NP hard so we just we've also shown that now quadratic programming is NP hard okay so we don't expect to be able to solve this quadratic program unless P equals NP so the sdp relaxation
1:18:27 is to maximize the sum over edges in e e is i j of 1 minus VI do VJ over 2 and for all I VI Dov is equal to one or sdp or VP you know it's the same thing
1:19:05 okay so we can solve this thing um quickly okay but now we don't get a bunch of minus ones and ones telling us left or right in the partition what we get is a bunch of unit vectors so now how do we actually turn those vectors into a part partition so the algorithm the Gman Williamson
1:19:31 algorithm is pick um a random hyperplane pick a random R in RN by the way remember from the way we got to Vector programming from sdp remember these V were The Columns of a matrix M they're n dimensional vectors so what we're going to do is we're going to pick random vectors R in RN pick a single random Vector R in RN
1:20:02 and put vertex I in s if the sign of R do VI is at least zero and we'll put vertex I in the the other side of the partition if the sign is negative okay so pick a random hyperplane and you're either above the hyper plane or below it and that decides what side of the partition you're
1:20:33 on okay so now in the last minute what's the expected what's the expected um size of the cut by doing this this is just the sum over edges is an e of the probability that um let's say e is i j the probability that I and J
1:21:06 are well VI and VJ are on opposite sides of R right but VI and VJ are just two vectors so we can draw them you know in they they span a two- dimensional space so we can draw them they're on the unit sphere they have Norm one so VI is
1:21:38 somewhere VJ is somewhere what's the probability that they're separated by this hyper plane well R has to be somewhere in here right so for them to be separated R had to be somewhere in here so there's an angle Theta
1:21:55 so the probability that e is separated is equal to I guess uh well I'm running out of time so well the probability that e is separated is theeta over pi which means that uh the probability separated over one minus vi. VJ over 2 is equal to this 2 over Pi um 2 over piun * Theta over 1 - Theta right vi.
1:22:54 VJ is exactly cosine Theta okay and so this is exactly where this ratio comes from okay and then you ask like what's the worst that this ratio could ever be well it's the INF over all Theta so I'm out of time but I mean that's basically how the algorithm goes maybe I'll fill in details a little more rigorously in the notes um but
1:23:22 that's it okay questions in the last few seconds yeah yeah I mean I just mean um I mean what's the probability that VI what's the probability that the sign of vi. R is not equal to the sign of vj. R
1:23:48 so by this I mean what's the probability that the sign of vi. r is not equal to the sign of VJ R all right so right yeah sorry yeah so I guess so um so r r is the normal to the hyper plane so um I guess what I meant is so if this is the hyper
1:24:33 plane then um in this picture R would be here I guess yeah sorry that picture was a little misleading right but the point is the hyper plane has to be somewhere in this window in order for you to be cut
1:24:54 okay so anyway enjoy the guest lectures next week