n this problem, you will solve the following classic problem of fractional set cover. Suppose you have a collection of m sets over a universe of size n, described by sets S1, . . . , Sm. You can also think of the collection as described by a matrix A, where Ai,j = 1 iff element j is in set i. Note that "integer set cover" asks to find a vector x {0, 1}n such that Ax 1 for each coordinate i and which minimises x1 = Pn j=1 xj . The fractional set cover problem relaxes this to finding a vector x [0, 1]n. The goal here is to find a 1 approximation to the fractional set cover problem: an x [0, 1]n such that Ax 1 and x1 is at most 1 more than the best possible (minimum) value of x1. We want to design a fast algorithm for the problem. Below, let s = |S1| . . . |Sm| n m be the size of the input. (a) First solve the following oracle problem: given a vector p Rm , find a vector x [0, 1]n such that