3. Maxcut The weighted maxcut problem is the following NP-complete problem. Given an undirected, weighted graph G with non-negative weights We on each edge e of the graph, find a cut of the vertices of the graph into 2 sets of vertices A and B, so that the sum of the weights of edges going from one side of the cut to the other is maximized. You may have seen the following extremely simple randomized algorithm: assign each vertex at uniformly at random to A to B with equal probability, Let E(A,B) denote the set of edges with one endpoint in A and the other endpoint in B. The weight of the cut is the sum of the weights of the edges that go across the cut. (i). What is the expected value of the weight of the cut you get in this way. You should write the expected weight of the cut in terms of the weights of the edges (ii). Now recall that if the expected value of a random variable is some value V then there must be value of that variable which is > V. Explain why this is true. (Again you need not give a proof of this (though you can if you like), but just give the intuition why this is true.) (iii). Show that max-cut has a 2 approximation, that is for any graph G there is a cut of G whose weight is at least 1/2 the size of the max cut of G. You can do this using parts one and (ii) above. Namely, explain why every weighted graph G has some cut whose value is a at least 1/2 of the maxcut of G. (You need not explain how to find this cut, just that there must exist a cut which gives you a 2-approximation of the max cut problem, that is a cut for which (2 x E(weight of the cut) > (the weight of the largest weight cut in G.) 3. Maxcut The weighted maxcut problem is the following NP-complete problem. Given an undirected, weighted graph G with non-negative weights We on each edge e of the graph, find a cut of the vertices of the graph into 2 sets of vertices A and B, so that the sum of the weights of edges going from one side of the cut to the other is maximized. You may have seen the following extremely simple randomized algorithm: assign each vertex at uniformly at random to A to B with equal probability, Let E(A,B) denote the set of edges with one endpoint in A and the other endpoint in B. The weight of the cut is the sum of the weights of the edges that go across the cut. (i). What is the expected value of the weight of the cut you get in this way. You should write the expected weight of the cut in terms of the weights of the edges (ii). Now recall that if the expected value of a random variable is some value V then there must be value of that variable which is > V. Explain why this is true. (Again you need not give a proof of this (though you can if you like), but just give the intuition why this is true.) (iii). Show that max-cut has a 2 approximation, that is for any graph G there is a cut of G whose weight is at least 1/2 the size of the max cut of G. You can do this using parts one and (ii) above. Namely, explain why every weighted graph G has some cut whose value is a at least 1/2 of the maxcut of G. (You need not explain how to find this cut, just that there must exist a cut which gives you a 2-approximation of the max cut problem, that is a cut for which (2 x E(weight of the cut) > (the weight of the largest weight cut in G.)