Question 4 (LP rounding; 10 marks) Recall the set cover problem discussed in class. We are given a universe (set) U-[x,..., x,), a collection S-SS of subsets of U, and a cost function c that assigns a positive cost c(S) to each set Si. Our goal was to find a minimum-cost subset eS such that every element in U is contained in at least one set in C The set multicover problem is an extension of the set cover problem where every element x, E U has an associated cover requirement r(x) N and we are to find a minimum-cost collection C of sets chosen from S such that every element x E U is contained in at least r(x) sets in C. The sets in S are allowed to be included more than once in C, that is, C is a multiset. Express the set multicover problem as an integer linear program and then apply randomized LP rounding to obtain an O(lgn)-approximation for this problem. Your algorithm should follow the same overall strategy as the randomized rounding approach for the set cover problem. There are two complications you will have to deal with. The first one is that the fractional frequency with which each set is chosen may not be between 0 and 1. If the fractional frequency of a set S in an optimal fractional solution is fs, you should immediately include Lfs] copies of S in the multicover you construct and then use the fractional part of fs as the probability for sampling as in the set cover algorithm. The second complication is not an algorithmic one but an analytical one. The analysis of the set cover algorithm only needed to bound the probability that a given element x EU is not covered by the computed subset of S at all. Here, you need to bound the probability that x is covered less than r(x) times. To do so elegantly, you should make use of the following result: Chernoff bound: Let X be a random variable that is the sum of independent binary variables X,,...,Xn (variables that take on values in (0, 1]). If uE[], then P[X s (1-5)u]se ay 081 Question 4 (LP rounding; 10 marks) Recall the set cover problem discussed in class. We are given a universe (set) U-[x,..., x,), a collection S-SS of subsets of U, and a cost function c that assigns a positive cost c(S) to each set Si. Our goal was to find a minimum-cost subset eS such that every element in U is contained in at least one set in C The set multicover problem is an extension of the set cover problem where every element x, E U has an associated cover requirement r(x) N and we are to find a minimum-cost collection C of sets chosen from S such that every element x E U is contained in at least r(x) sets in C. The sets in S are allowed to be included more than once in C, that is, C is a multiset. Express the set multicover problem as an integer linear program and then apply randomized LP rounding to obtain an O(lgn)-approximation for this problem. Your algorithm should follow the same overall strategy as the randomized rounding approach for the set cover problem. There are two complications you will have to deal with. The first one is that the fractional frequency with which each set is chosen may not be between 0 and 1. If the fractional frequency of a set S in an optimal fractional solution is fs, you should immediately include Lfs] copies of S in the multicover you construct and then use the fractional part of fs as the probability for sampling as in the set cover algorithm. The second complication is not an algorithmic one but an analytical one. The analysis of the set cover algorithm only needed to bound the probability that a given element x EU is not covered by the computed subset of S at all. Here, you need to bound the probability that x is covered less than r(x) times. To do so elegantly, you should make use of the following result: Chernoff bound: Let X be a random variable that is the sum of independent binary variables X,,...,Xn (variables that take on values in (0, 1]). If uE[], then P[X s (1-5)u]se ay 081
