# How to implement GREEDY-SET-COVER in a way that it runs in linear time [closed]

This is an exercise in the book Introduction to Algorithm, 3rd Edition.

The original question is:

Show how to implement GREEDY-SET-COVER in such a way that it runs in time $O(\sum_{S\in\mathcal{F}}|S|)$.

The GREEDY-SET-COVER in the text book is as follows: Definition for $(X,\mathcal{F})$ is given as: • What have you tried? Where did you get stuck? How far is the current implementation from what the question asks for? Oct 16, 2013 at 17:56

Here is some Python code that should implement Greedy Set Cover in linear time:

(Warning, it empties the input sets during the processing!)

from collections import defaultdict

F = [set([1,2,3]),
set([3,4,5,6]),
set()]

# First prepare a list of all sets where each element appears
D = defaultdict(list)
for y,S in enumerate(F):
for a in S:
D[a].append(y)

L=defaultdict(set)
# Now place sets into an array that tells us which sets have each size
for x,S in enumerate(F):

E=[] # Keep track of selected sets
# Now loop over each set size
for sz in range(max(len(S) for S in F),0,-1):
if sz in L:
P = L[sz] # set of all sets with size = sz
while len(P):
x = P.pop()
E.append(x)
for a in F[x]:
for y in D[a]:
if y!=x:
S2 = F[y]
L[len(S2)].remove(y)
S2.remove(a)

• Don't we need to update D in the inner loop? That is, when we removea from S2, shouldn't we also remove S2 from D[a]? Oct 10, 2018 at 18:15
• Ah, I see, because a is removed from all sets right after D[a] is read. Oct 10, 2018 at 21:41