Budgeted Maximum Coverage

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.

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;};

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

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

equals to \( 1-1/e \).

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

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

Generated on Tue Jan 31 2017 00:30:51 by 1.8.5