Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

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


© 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

×