$(28$ points$)4.$ NP$-$completeness proof and approximation algorithm design

The Set$-$Cover Problem: Given a set $U$ of $n$ elements and a list $S_1,$cdots,$S_m$ of subsets of $U,$ where

each set $S_i$ has an associated weight $w_{i}0,$ the goal is to find a set cover $C($i$.$e$.,U={?}_{S_i\text{i}\text{n}\text{C}}{S}_i)$

so that the total weight ${\displaystyle \underset{S_i\text{i}\text{n}\text{C}}{\overset{?}{}}}{w}_i$ is minimized. Here, a set cover is a collection of these sets whose

union is equal to all of $U.$

$(10$ points$)4\mathrm{.}1$ Please prove that the Set$-$Cover problem is NP$-$complete.

Hint: reference to Section $34\mathrm{.}5$ in the textbook

$(2$ points$)4\mathrm{.}1\mathrm{.}1$ Formulate a related decision problem for the Set$-$Cover problem.

$(2$ points$)4\mathrm{.}1\mathrm{.}2$ Show that the Set$-$Cover problem belongs to the NP$.$

$(6$ points$)4\mathrm{.}1\mathrm{.}3$ A vertex cover of an undirected graph is a subset $V^{\text{'}}$subeV such that if

$(u,v)inE,$ then $in{V}^{\text{'}}$ or $vin{V}^{\text{'}}($or both$).$ The Vertex$-$Cover problem is to find a vertex cover

of minimum size in a given graph. The decision problem of this optimization problem asks

whether a graph has a vertex cover of a given size $k.$ The Vertex$-$Cover problem is NP$-$complete

as shown in Theorem $34\mathrm{.}12.$ Please prove that the Vertex$-$Cover problem is polynomial$-$time

reducible to the Set$-$Cover Problem.

$(18$ points$)4\mathrm{.}2$ Please design an approximation algorithm with an approximate rate of no more

than $1+lnmax|S_i|$ using a greedy method to solve the Set$-$Cover problem.

Hint: reference to Subsection $35\mathrm{.}3$ in the textbook

$(6$ points$)4\mathrm{.}2\mathrm{.}1$ Describe the basic idea of your approximation algorithm in pseudocode.

$(12$ points$)4\mathrm{.}2\mathrm{.}2$ Prove its approximate rate by computing the upper bound of its solution, which

is at most of the optimum.