Budgeted Maximum Coverage

# Problem definition.

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.

# Solution

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

example:

#include <iostream>
#include <vector>
#include <iterator>
#include <boost/range/irange.hpp>
int main() {
std::vector<std::vector<int>> set_to_elements = {
{ 1 }, { 2 }, { 0, 1 }, { 2, 3, 4 }
};
std::vector<int> set_to_cost = { 1, 1, 5, 5 };
std::vector<int> element_to_weight = { 3, 5, 1, 1, 1 };
const int BUDGET = 10;
auto sets = boost::irange(0, 4);
std::vector<int> result;
auto element_index = [](int el){return el;};
sets,
[&](int set){return set_to_cost[set];},
[&](int set){return set_to_elements[set];},
back_inserter(result),
element_index,
BUDGET,
[&](int el){return element_to_weight[el];});
std::cout << "Covered: " << covered << std::endl;
}

complete example is budgeted_maximum_coverage_example.cpp

## Parameters

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

## Approximation Ratio

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

## The complexity

Complexity of the algorithm is $$E*log(|$$$$S$$ $$|)*|$$$$S$$ $$|^{|I|}$$. where $$E$$ is number of elements in all sets and $$I$$ is initial set size

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