In weighted set cover problem we are given Universe \(U\) and family \(S\) of subsets of U, a cover is a subfamily \(C\subseteq S\) of sets whose union is \(U\). The goal is to find minimum cost cover.
Here we implement the following algorithm:
At each stage we add to \(C\) a set which maximizes(number of uncovered elements)/(cost of set).
We repeat the step as long as uncovered elements exist. When the algorithm finishes we return selected sets in \(C\).
complete example is set_cover_example.cpp
IN: SetIterator sets_begin
IN: SetIterator sets_eEnd,
IN: GetCostOfSet set_to_cost
IN: GetElementsOfSet set_to_elements
OUT: OutputIterator result
The Iterators of selected Sets will be output to the output iterator result
The iterator type must be a model of Output Iterator
IN: GetElementIndex get_el_index we need in algorithm map elements to small unique integers
equals to \(H(s')\) where \(s'\) is the maximum cardinality set of \(S\) and \(H(n)\) is n-th harmonic number.
Complexity of the algorithm is \(|I|*log(|I|)\). where \(I\) is number of elements in all sets
Memory complexity of the algorithm is \(|I|\). where \(I\) is number of elements in all sets
The algorithm analysis is described in