# 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? Commented 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([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)

print E


It uses a dictionary D to store a list of all sets with a particular element.

It uses an array E to store which sets currently have each size. In other words, E[sz] will contain information about all the sets that currently have exactly sz elements.

The key to showing that this is linear is to observe that the innermost loop removes an element from a set, so cannot be executed more times than the total number of elements in all sets.

• 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]? Commented Oct 10, 2018 at 18:15
• D[a] will only be used once, when element a is being removed. If you wanted, you could certainly del D[a] after use. This will free up memory a bit faster, but add a little more computation. Commented Oct 10, 2018 at 18:21
• Ah, I see, because a is removed from all sets right after D[a] is read. Commented Oct 10, 2018 at 21:41
• What would a Matlab implementation look like ? Commented Jan 2 at 16:32