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).
© 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