In the below instance of set cover. How many sets the greedy algorithm will pick?. All sets have cost 1.
Can anyone explain me. What is the solution for this question.
So how will be greedy algorithm works for the 2nd instance.
how many sets it picks in the instance.
Considering that greedy algorithm selects the best set each time if it this is determined by the number of points in each set it would first take the largest.
After it takes one it will remove the points which overlap from the remaining sets and again select the largest. So the remaining set would look like:
Therefore it should be 3 sets in the folding order:
This is a good problem which illustrates how it doesn't perform optimally because there is a possibility to solve the problem by taking only 2 sets. You can read a bit more here: http://pages.cs.wisc.edu/~shuchi/courses/787-F07/scribe-notes/lecture02.pdf