Maximum Coverage

# Problem definition.

In budgeted maximum coverage we are given Universe $$U$$ and family $$S$$ of subsets of $$U$$. Each element e in $$U$$. has weight w(e) We are also given number $$k$$

The goal if to find subfamily $$C\subseteq S$$ that has size not greater than k and maximize weight of covered elements.

# Solution

We use the following algorithm:

At each stage we add to $$C$$ a set witch maximizes (weight of uncovered elements)/(cost of set).

We repeat the step as long as number of selected sets is smaller than k.

example:

#include <iostream>
#include <vector>
#include <iterator>
#include <boost/range/irange.hpp>
int main() {
std::vector<std::vector<int>> set_to_elements = {
{ 1, 2 },
{ 3, 4, 5, 6 },
{ 7, 8, 9, 10, 11, 12, 13, 0 },
{ 1, 3, 5, 7, 9, 11, 13 },
{ 2, 4, 6, 8, 10, 12, 0 }
};
const int NUMBER_OF_SETS_TO_SELECT = 2;
auto sets = boost::irange(0, 5);
using SetIterator = decltype(sets)::iterator;
std::vector<int> result;
auto element_index = [](int el){return el;};
sets,
[&](int set){return set_to_elements[set];},
back_inserter(result),
element_index,
NUMBER_OF_SETS_TO_SELECT);
std::cout << "Covered: " << covered << std::endl;
}

complete example is max_coverage_example.cpp

## Parameters

IN: SetIterator sets_begin

IN: SetIterator sets_end,

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: unsigned int number_of_sets_to_select

IN: GetWeightOfElement element_to_weight =GetWeightOfElement()

## Approximation Ratio

equals to $$1-1/e$$.

## The complexity

Complexity of the algorithm is $$E*log(|S|)$$. where $$E$$ is number of elements in all sets and $$S$$ is number of sets

Memory complexity of the algorithm is $$E$$. where $$E$$ is number of elements in all sets

## References

The algorithm analysis is described in Cohen:2008:GMC:1401272.1401544