Set Cover

Problem definition.

In weighted set cover problem we are given Universe \(U\) and family \(S\) of subsets of U, a cover is a subfamily \(C\subseteq S\) of sets whose union is \(U\). The goal is to find minimum cost cover.

Solution

Here we implement the following algorithm:

At each stage we add to \(C\) a set which maximizes(number of uncovered elements)/(cost of set).

We repeat the step as long as uncovered elements exist. When the algorithm finishes we return selected sets in \(C\).

example:

#include <iostream>
#include <vector>
#include <iterator>

#include <boost/range/irange.hpp>

#include "paal/greedy/set_cover/set_cover.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 }
    };
    std::vector<int> costs = { 1, 1, 1, 1, 1 };
    auto sets = boost::irange(0, 5);
    std::vector<int> result;
    auto element_index = [](int el){return el;};
    auto cost = paal::greedy::set_cover(sets,
                                        [&](int set){return costs[set];},
                                        [&](int set){return set_to_elements[set];},
                                        back_inserter(result),
                                        element_index);
    std::cout << "Cost: " << cost << std::endl;
}

complete example is set_cover_example.cpp

Parameters

IN: SetIterator sets_begin

IN: SetIterator sets_eEnd,

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

Approximation Ratio

equals to \(H(s')\) where \(s'\) is the maximum cardinality set of \(S\) and \(H(n)\) is n-th harmonic number.

The complexity

Complexity of the algorithm is \(|I|*log(|I|)\). where \(I\) is number of elements in all sets

Memory complexity of the algorithm is \(|I|\). where \(I\) is number of elements in all sets

References

The algorithm analysis is described in [22]