5. The problem Minimum-Weighted Hitting Set is a generalization of the Minimum- Weighted Vertex Cover: Its input consist

[answerhappygod]

5 The Problem Minimum Weighted Hitting Set Is A Generalization Of The Minimum Weighted Vertex Cover Its Input Consist 1 (48.61 KiB) Viewed 23 times

5. The problem Minimum-Weighted Hitting Set is a generalization of the Minimum- Weighted Vertex Cover: Its input consists of n positive costs G; for 1 sisn, and m non-empty subsets E; of {1, 2,..., n} for 1 <j <m. A hitting set of this instance is a subset U of {1,2,...,n} such that U nE; # for each 1 Sj sm. The objective is to compute a a hitting set U with minimum total cost Lieu Ci. Give a polynomial-time approximation algorithm for this problem with approximation bound A := maxi<j<m Ejl.