The Hitting Set problem is similar to the Set Cover problem. An instance is given by a list Si, , Sn C1,,m- U of n subsets of a universe U of size Um. In the Set Cover problem we want to find a minimum size subset of sets S C 1,, n which covers the universe U i.e Uies SU. In the Hitting Set problem we are given an absolute upper bound k on the number of sets in S and we are asked to marimize the number of elements covered by S i.e Uies Si. The search version of the Hitting Set problem is NP-Hard (you dont need to prove this) 1. Let V* -Uies. Si denote the items covered by the optimal solution the Hitting Set problem. Given a set P C (1,,n] define Uncovered(V",P) - V\ (UiEp S) and let np - Uncovered(V, P)l denote the number of elements in V* that are still uncovered by a Hitting Set solution P. Show that for any subset P C11,,n} there exists some j f P s.t. the set S, covers at least np/k of the remaining items in Uncovered(V*. P 2. Develop a greedy algorithm that always returns a hitting set solution which always covers at least (1 - 1/e)|V* where |V is the number of items covered in the optimal solution. (Hint: You may use without proof the fact that (1 1/k)e1 for all integers k,x > 0. ) The Hitting Set problem is similar to the Set Cover problem. An instance is given by a list Si, , Sn C1,,m- U of n subsets of a universe U of size Um. In the Set Cover problem we want to find a minimum size subset of sets S C 1,, n which covers the universe U i.e Uies SU. In the Hitting Set problem we are given an absolute upper bound k on the number of sets in S and we are asked to marimize the number of elements covered by S i.e Uies Si. The search version of the Hitting Set problem is NP-Hard (you dont need to prove this) 1. Let V* -Uies. Si denote the items covered by the optimal solution the Hitting Set problem. Given a set P C (1,,n] define Uncovered(V",P) - V\ (UiEp S) and let np - Uncovered(V, P)l denote the number of elements in V* that are still uncovered by a Hitting Set solution P. Show that for any subset P C11,,n} there exists some j f P s.t. the set S, covers at least np/k of the remaining items in Uncovered(V*. P 2. Develop a greedy algorithm that always returns a hitting set solution which always covers at least (1 - 1/e)|V* where |V is the number of items covered in the optimal solution. (Hint: You may use without proof the fact that (1 1/k)e1 for all integers k,x > 0. )
