Tags

By year

  1. 2019 (1)
  2. 2018 (2)
  3. 2017 (4)
  4. 2015 (9)

Greedy Set Cover Sample Implementation

C++ Algorithm Snippet

Posted on Aug 18

Problem Statement

Set cover problem: Given the universe \(\mathcal{U}\) and the set \(\mathcal{S}\) of subsets of \(\mathcal{U}\), find the collection \(\mathcal{C}\) of subsets from \(\mathcal{S}\) that covers the universe while minimizing the total cost where

\begin{align} \mathcal{U} &= \{ 1,2,\cdots,n \} \\ \bigcup_{s\in\mathcal{S}} s &= \mathcal{U} \\ \bigcup_{s\in\mathcal{C}} s &= \mathcal{U} \end{align}

and the objective is to …

\[ \text{minimize}\qquad {\sum_{s\in\mathcal{C}}\mathrm{cost}{(s)}} \]

Sample Implementation

Input

The format of the problem input for the above code is:

  • [the cardinality of the universe] [the number of the subsets given below]
  • [cost of the subset 0] [the size of the subset 0] [the first element] ...
  • [cost of the subset 1] [the size of the subset 1] [the first element] ...
  • ...

Run

The following snippet shows the usage of the greedy_set_cover class. It takes an input from an input stream and translates the input into its internal parameters, the universe cardinality and the subsets, according to the input format above.

  greedy_set_cover sc;
  istringstream iss(src); // Input string in the above input format.

  sc.input(iss); // Feed the input.
  sc.solve(); // Solve the problem.

The solve method show the selection of subsets, each represented with an 0-based integer, and the total cost incurred by that selection.

Greedy Algorithm

The implementation is roughly summarized as a pseudo code below:

  • GREEDY-SET-COVER(\(\mathcal{U}\), \(\mathcal{S}\), \(\mathrm{cost}\)):
    • \(\mathrm{COVERED} \leftarrow \Phi\) // Elements covered so far.
    • \(\mathcal{C} \leftarrow \Phi\)
    • \(\mathrm{COST} \leftarrow 0\) // Total cost so far.
    • WHILE \({|\mathrm{COVERED}|} \lt {|\mathcal{U}|} \):
      • \(s \leftarrow \mathrm{argmin}_{s\in\mathcal{S}} { \frac{\mathrm{cost}{(s)}}{|{s - \mathrm{COVERED}}|} } \)
      • \(\mathrm{COVERED} \leftarrow \mathrm{COVERED} \cup s \)
      • \(\mathcal{C} \leftarrow \mathcal{C} \cup \{s\} \)
      • \(\mathrm{COST} \leftarrow \mathrm{COST} + \mathrm{cost}{(s)} \)
    • RETURN \(\mathrm{COST},\ \mathcal{C}\)

2015 My gh-pages