Consider the Weighted Independent Set problem. Input: an undirected graph G=(V,E) with weights wv0 on each vertex. Output: an independent set of maximum weight. This problem is known to be NP-hard. Consider the following randomized design: - Sort the vertices at random, v1,v2,,vn. - S= - For i=1 to n : if vi is not adjacent to any vertex in S,S:=S{vi}. Denote by the maximum degree of the graph. Show that the expected total weight of the return S is at least +11 times the weight of the optimal (i.e.: max weight) independent set. Hint: let w(S) be the random variable that denotes the weight of the return of this design. Write this r.v. as a linear combination of Bernoulli r.v.s., one for each vertex and apply linearity of expectation