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>

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