We argued in class that the greedy approach to solving the unweighted Set Cover problem achieves an approximation ratio of O(Hn). 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 Hn 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).
© 2022 • Neeldhara Misra • Credits •
Corrections? Please leave a comment here or a PR in this repository, thanks!
I’d rather be a failure at something I love than a success at something I hate.
George Burns
You live and you learn — at any rate, you live.
Douglas Adams
A problem worthy of attack proves its worth by fighting back.
Paul Erdos