Approx Greedy Set-Cover

is an Approximation Algorithm for solving the Approx Greedy Set Cover.

It uses a greedy method by, at each stage, picking the set $S$ that covers the largest numbers of remaining elements that are uncovered.

Pseudocode

The algorithm takes as input the set of elements to be covered $X$ and a family of subsets $\mathcal{F}$ of $X$.

def approx_greedy_set_cover(X, F):
    U = set(X)  # Initialize U as the universal set X
    C = set()   # Initialize C as an empty set
 
    while U:  # While U is not empty
        # Select the set S in F that maximizes |S ∩ U|
        S = max(F, key=lambda s: len(s & U))
        U -= S  # Update U by removing the elements of S
        C.add(frozenset(S))  # Add S to C (using frozenset to make it hashable)
 
    return C

Runs in $O(|X||\mathcal{F}|\min (|X|,|\mathcal{F}|))$ time.

Theorems

The algorithm is a polynomial-time ρ(n)-Approximation Algorithm, where $\rho (n)=H(\max |S|:S\in \mathcal{F})$

Proof

See CLRS 1119