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>
#include "paal/greedy/set_cover/budgeted_maximum_coverage.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;};
    auto covered = paal::greedy::budgeted_maximum_coverage(
        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