Courses
  • IITGN
  • Online
  • Short Courses
  • Other

CS614. Advanced Algorithms. L10 Quiz.

CS614. Advanced Algorithms.

L10 Quiz

Back to the course page

Problem 1. Set Cover: The Greedy Bound is Tight

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.

Problem 2. Set Cover and Related Problems
  1. Show that Vertex Cover is a special case of Set Cover.

  2. Also show that Dominating Set and Set Cover are equivalent (i.e, Set Cover can be reduced to Dominating Set and vice versa).

Made with Quarto and 🩶

 

Content by Neeldhara Misra