[10 marks] This problem is about a weighted version of the Set Cover problem. The input consists of: a set E of n elements, where each e E has a non-negative weight w(e); a collection S1, . . . , Sk where Si E; and a number t. The problem is to pick t of the subsets Si to maximize the sum of the weights of the elements covered. The goal of this question is to show that the obvious greedy algorithm has approximation factor 1 1 e where e is Eulers constant. The greedy algorithm first picks a set that covers the maximum weight of elements, then deletes those elements and repeats until t sets have been chosen. In other words, at each step the algorithm picks a set that has the maximum weight of uncovered elements. Note that ties are broken arbitrarily. Let W be the weight of the elements covered by the optimum solution. Let Wi , for i = 1, . . . t, be the weight of the elements covered by the first i sets of the greedy algorithm. Thus Wt is the final weight of the greedy solution. (a) [2 marks] (Warm up questions to gain intuition.) Find an example with t = 2 and unit weights where W2 = 3 4W . Explain why you cannot have an example with t = 2 and unit weights where W2 1 2W . (b) [4 marks] Prove that W1 W/t. More generally, prove that Wi Wi1 (W Wi1)/t. (c) [4 marks] Prove by induction that Wi (1 (1 1 t ) i )W . (d) [0 marks] From part (c), the weight of the greedy solution, Wt , is at least (1(1 1 t ) t )W . Since limt(1(1 1 t ) k t) = 1 1 e and 1(1 1 t ) t is decreasing, thus 1(1 1 t ) t 1 1 e , so the approximation ratio of the greedy algorithm is 1 1 e . In fact 1 1 e is the best approximation factor possible for this problem (unless P=NP).

2. 10 marks] This problem is about a weighted version of the Set Cover problem. The input consists of: a set E of n elements, where each e E has a non-negative weight w(e); a collection S1,... , Sk where Si C E; and a number t. The problem is to pick t of the subsets Si to maximize the sum of the weights of the elements covered The goal of this question is to show that the obvious greedy algorithm has approximation factor 1- where e is Euler's constant. The greedy algorithm first picks a set that covers the maximum weight of elements, then deletes those elements and repeats until t sets have been chosen. In other words, at each step the algorithm picks a set that has the maximum weight of uncovered elements. Note that ties are broken arbitrarily Let W* be the weight of the elements covered by the optimum solution. Let W, fori 1,...t, be the weight of the elements covered by the firsti sets of the greedy algorithm. Thus Wt is the final weight of the greedy solution [2 marks] (Warm up questions to gain intuition.) Find an example with t 2 and unit weights where W2 - W. Explain why you cannot have an example with t unit weights where W2 W (a) 2 and (b) [4 marks] Prove that Wi 2 W*/t. More generally, prove that Wi - Wi- 2 (W Wi-1)/t (c) (4 marks] Prove by induction that W 2 (1-(1 (d) [0 marks] From part (c), the weight of the greedy solution, Wi, is at least 1)w Since limt oo(1-(1-1)kt)-1-1 and 1-(1-1)t s decreasing, thus 1-0-)t so the approximation ratio of the greedy algorithm is 1-. 1-1, In fact 1 is the best approximation factor possible for this problem (unless P NP) 2. 10 marks] This problem is about a weighted version of the Set Cover problem. The input consists of: a set E of n elements, where each e E has a non-negative weight w(e); a collection S1,... , Sk where Si C E; and a number t. The problem is to pick t of the subsets Si to maximize the sum of the weights of the elements covered The goal of this question is to show that the obvious greedy algorithm has approximation factor 1- where e is Euler's constant. The greedy algorithm first picks a set that covers the maximum weight of elements, then deletes those elements and repeats until t sets have been chosen. In other words, at each step the algorithm picks a set that has the maximum weight of uncovered elements. Note that ties are broken arbitrarily Let W* be the weight of the elements covered by the optimum solution. Let W, fori 1,...t, be the weight of the elements covered by the firsti sets of the greedy algorithm. Thus Wt is the final weight of the greedy solution [2 marks] (Warm up questions to gain intuition.) Find an example with t 2 and unit weights where W2 - W. Explain why you cannot have an example with t unit weights where W2 W (a) 2 and (b) [4 marks] Prove that Wi 2 W*/t. More generally, prove that Wi - Wi- 2 (W Wi-1)/t (c) (4 marks] Prove by induction that W 2 (1-(1 (d) [0 marks] From part (c), the weight of the greedy solution, Wi, is at least 1)w Since limt oo(1-(1-1)kt)-1-1 and 1-(1-1)t s decreasing, thus 1-0-)t so the approximation ratio of the greedy algorithm is 1-. 1-1, In fact 1 is the best approximation factor possible for this problem (unless P NP)