In budgeted maximum coverage we are given Universe \(U\) and family\(S\) of subsets of \(U\). Each set s in \(S\) has cost c(s) and each element e in \(U\) has weight w(e). We are also given budget \(B\)
The goal if to find subfamily \(C\subseteq S\) that has cost not greater than B and maximize weight of covered elements.
We use the following procedure:
At each stage we add to \(C\) a set which doesn't exceed the budget and which maximizes (weight of uncovered elements)/(cost of set)
We repeat the step as long as such set exists.
Here we implement the following algorithm:
We start above procedure from every initial_set_size \(I\) of set selected
and return best from (all \(K!/(K-I)!/I!\)) found solution
complete example is budgeted_maximum_coverage_example.cpp
IN: SetIterator sets_begin
IN: SetIterator sets_end,
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
IN: Budget budget
IN: GetWeightOfElement element_to_weight =GetWeightOfElement()
IN: unsigned int initial_set_size =3
equals to \( 1-1/e \).
Memory complexity of the algorithm is \(E\). where \(E\) is number of elements in all sets
The algorithm analysis is described in Cohen:2008:GMC:1401272.1401544