# 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:

## closed as unclear what you're asking by D.W.♦, frafl, Realz Slaw, Luke Mathieson, JuhoOct 30 '13 at 10:05

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• What have you tried? Where did you get stuck? How far is the current implementation from what the question asks for? – Yuval Filmus Oct 16 '13 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([2])]

# 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]? – Elliot Gorokhovsky Oct 10 '18 at 18:15
• Ah, I see, because a is removed from all sets right after D[a] is read. – Elliot Gorokhovsky Oct 10 '18 at 21:41