4. For any positive integer n let [n] = {1, 2, ...,n}. Let F be any collection of subsets of [n]. [10] A hitting set for F is any subset U C [n] such that for all S EF, UNS +). Consider the following linear program that solves the hitting set problem. In the linear program below there is a variable x; for all i E [n]. min Xi ie[n] subject to li > 1, VSEF >0, Vi e [n] LES Xi (a) Construct the dual to this linear program. Give an intuitive description of the problem that the dual solves. (b) Now we show that the linear program performs poorly when solving the hitting set problem. For any family F let LP(F) denote the optimal objective value of the above linear program, and let H(F) denote the size of the smallest hitting set for F. For all positive integers k and n, construct a family Fn of subsets of [n] such that |S| 1, VSEF >0, Vi e [n] LES Xi (a) Construct the dual to this linear program. Give an intuitive description of the problem that the dual solves. (b) Now we show that the linear program performs poorly when solving the hitting set problem. For any family F let LP(F) denote the optimal objective value of the above linear program, and let H(F) denote the size of the smallest hitting set for F. For all positive integers k and n, construct a family Fn of subsets of [n] such that |S|