AlgoVerse

Greedy set cover

Each time, take the set covering the most elements not yet covered; at most H(max |S|) ≈ ln n times the fewest sets possible.

There is a universe X and a family of its subsets. We want the fewest subsets that together cover all of X (the fewest experts who between them have every skill, say). The problem is NP-hard.

Read the full explanation ↓
Input:
S 6×12PDF export

12 elements and 6 sets (the CLRS example); greedy takes 4 sets where 3 would do.

  1. def greedy_set_cover(S):
  2. # S[i][e] = 1 when set i contains element e (elements are numbered from 1 in the picture).
  3. m = len(S)
  4. n = len(S[0])
  5. sets = []
  6. for row in S:
  7. sets.append([e + 1 for e in range(n) if row[e] == 1])
  8. universe = sorted(set(e for s in sets for e in s))
  9. left = list(universe)
  10. chosen = []
  11. rows = [["S" + str(i + 1), sets[i], len(sets[i])] for i in range(m)] # for the picture: set, elements, new ones
  12. count = len(left)
  13. while left:
  14. best = 0
  15. for i in range(m):
  16. new = len([e for e in sets[i] if e in left])
  17. rows[i][2] = new
  18. if new > len([e for e in sets[best] if e in left]):
  19. best = i
  20. chosen.append("S" + str(best + 1))
  21. left = [e for e in left if e not in sets[best]]
  22. return chosen

Invariant: The chosen sets cover exactly the elements outside left.

Start

left—
chosen—

The table is still empty.

Local variables

Orange = changed in this step

S list

[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0][1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0][0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0][0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1][0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]

Call stack

  1. greedy_set_cover()line 1
Step 1 of 145
Black = pick · Orange = key stepstart: 0/1 · pick: 0/4 · cover: 0/1
    Explanation

    The problem

    There is a universe X and a family of its subsets. We want the fewest subsets that together cover all of X (the fewest experts who between them have every skill, say). The problem is NP-hard.

    The greedy algorithm

    While some element is uncovered, take the set covering the most uncovered elements.

    The guarantee

    CLRS proves that greedy uses at most H(d) times the optimal number of sets, where d is the size of the largest set and H(d) = 1 + 1/2 + … + 1/d ≈ ln d. So it is a (ln n + 1)-approximation. It has been shown that (assuming P ≠ NP) no much better approximation is possible.

    The input

    S is an incidence matrix: row i is the set S_i and column e the element e; a 1 means the element is in the set.