Page 1 of 1
5. The problem Minimum-Weighted Hitting Set is a generalization of the Minimum- Weighted Vertex Cover: Its input consist
Posted: Mon May 09, 2022 6:30 am
by 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 25 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.