| RcppGreedySetCover-package {RcppGreedySetCover} | R Documentation |
Fast Greedy Set Cover
Description
This package offers an implementation of the greedy algorithm for the set cover problem using Rcpp.
Set Cover Problem
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.
References
Vazirani, Vijay V. (2001), Approximation Algorithms, Springer