Eu vim com a seguinte implementação para o Greedy Set Cover depois de muita discussão sobre minha pergunta originalaqu. Com a ajuda que recebi, codifiquei o problema em uma "Cobertura de conjunto ganancioso" e depois de receber mais ajudaaqu, Vim com a seguinte implementação. Sou grato a todos por me ajudarem com isso. A implementação a seguir funciona bem, mas eu quero torná-la escalável / mais rápid

Por escalável / mais rápido, quero dizer que:

O meu conjunto de dados contém cerca de 50K-100K conjuntos em S O número de elementos em U em si é muito pequeno na ordem de 100-500 O tamanho de cada conjunto em S pode estar entre 0 e 40

E aqui vai a minha tentativa:

U = set([1,2,3,4])
R = U
S = [set([1,2]), 
     set([1]), 
     set([1,2,3]), 
     set([1]), 
     set([3,4]), 
     set([4]), 
     set([1,2]), 
     set([3,4]), 
     set([1,2,3,4])]
w = [1, 1, 2, 2, 2, 3, 3, 4, 4]

C = []
costs = []

def findMin(S, R):
    minCost = 99999.0
    minElement = -1
    for i, s in enumerate(S):
        try:
            cost = w[i]/(len(s.intersection(R)))
            if cost < minCost:
                minCost = cost
                minElement = i
        except:
            # Division by zero, ignore
            pass
    return S[minElement], w[minElement]

while len(R) != 0:
    S_i, cost = findMin(S, R)
    C.append(S_i)
    R = R.difference(S_i)
    costs.append(cost)

print "Cover: ", C
print "Total Cost: ", sum(costs), costs

Não sou especialista em Python, mas qualquer otimização específica para este código seria muito bo