2
$\begingroup$

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:

greedy-set-cover-in-text-book

Definition for $(X,\mathcal{F})$ is given as:

enter image description here

$\endgroup$

closed as unclear what you're asking by D.W., frafl, Realz Slaw, Luke Mathieson, Juho Oct 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.

  • 1
    $\begingroup$ What have you tried? Where did you get stuck? How far is the current implementation from what the question asks for? $\endgroup$ – Yuval Filmus Oct 16 '13 at 17:56
4
$\begingroup$

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):
    L[len(S)].add(x)

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)
                        L[len(S2)].add(y)

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.

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.