Description Set Cover Problem References
This package offers an implementation of the greedy algorithm for the set cover problem using Rcpp.
We are given a universe of elements U and F, a collection of subsets from U, covering U; i.e. U is in the union of the sets in F. The objective is to find A, the smallest subcollection of F, covering U. An important application is hospital placement, where the number of hospitals is minimized under the constraint that all residents are provided for.
The optimal solution to the problem is available via linear programming, however this is not a feasible solution for large problems due to the computational demands involved. A quick approximate solution is given by the greedy algorithm. The algorithm iterates the following steps until all elements are covered, starting from an empty A:
Add the largest set of uncovered elements to A.
Remove covered elements from F.
This simple algorithm exhibits surprisingly good properties. For a nice introduction to the set cover problem and the greedy algorithm see Vazirani, 2001.
Vazirani, Vijay V. (2001), Approximation Algorithms, Springer
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.