Greedy Set Cover Approximation Ratio

Problem

Compare greedy set cover with the exact optimum on a small instance and return [greedy_count, optimal_count, ratio].

The universe is 0 to universe_size - 1 and greedy always takes the set covering the most uncovered elements, breaking ties by smallest index; the optimum is found by trying subsets in increasing size. Return [0, 0, 0.0] when the sets cannot cover the universe.

Hint

Greedy can be forced to pick small sets early; the harmonic bound is the worst case.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,3],[3,0]]]

expected: [2,2,1]

case 2

in: [5,[[0,1,2,3],[0,1],[2,3],[4],[3,4]]]

expected: [2,2,1]

case 3

in: [5,[[0,2,3],[0,2,4],[3],[1,3]]]

expected: [3,2,1.5]

case 4

in: [5,[[0,3],[0,3,4],[0,1,4],[2,3,4]]]

expected: [3,2,1.5]

case 5

in: [4,[[0,1],[1,2]]]

expected: [0,0,0]

Starter codePython

import itertools


def greedy_set_cover_ratio(universe_size, sets):
    # Your code here
    pass

5 test cases · run your code against them in the editor