We argued in class that the greedy approach to solving the unweighted Set Cover problem achieves an approximation ratio of \(O(H_n)\). Argue that this bound is tight, i.e, come up with examples where the algorithm picks sets in a manner that the cost of the solution is roughly \(H_n\) worse than optimal.
Show that Vertex Cover is a special case of Set Cover.
Also show that Dominating Set and Set Cover are equivalent (i.e, Set Cover can be reduced to Dominating Set and vice versa).