Greedy algorithm set cover
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
- Storing revision changes of a message
- Reversing characters of string of parenthesis to achieve at max H string depth
- How do you detect Credit card type based on number?
- Efficiently determine the parity of a permutation
- In MS Access using VBA: I want to transfer records with less than N^2 time complexity
- Longest increasing subsequence
- Using ranking data in Logistic Regression
- How to generated N numbers in array that sum of these numbers is equal to 0
- Delete nodes in singly linked list (two implementations)
- The "guess the number" game for arbitrary rational numbers?
- Max Heap finding kth smallest elements
- Checking if a word in string contains a palindrome
- Generate read-address and write address for zig-zag scan of NxN matrix
- algorithm using recursive function
- graph_to_gdfs not working even with simple examples
- Single Source - Single Destination Shortest Path (DFS + DP) - Time complexity?
- Distribute Coins in Binary Tree
- Quicksort with Python
- Discrete mathematics: Simulate the probability question
- How can I create all combinations of this object's keys/values in JavaScript?
- Why does the xorshift random number generator always seem to use these specific shifts?
- Efficient algorithm for detecting cycles in a directed graph
- How does a 'diff' algorithm work, e.g. in VCDIFF and DiffMerge?
- Find minimum sum from given array
- Javascript twoSum algorithm: Given an array of integers, return indices of the two numbers such that they add up to a specific target
- Split String into smaller Strings by length variable
- Bubble sort does not sort as expected
- Shortening list of numbers with hyphens between consecutive numbers
- Adjacent items in Quicksort's output: Does the algorithm guarantee they have been directly compared?
- The simplest way to write a unit conversion program