Bounded-Set-Size Set Cover Approximation Algorithm

Definition

Bounded-Set-Size Set Cover Approximation Algorithm

For a feasible Minimum Set Cover instance with $|S_j|\le d$ for every input set and $d\ge 1$, repeatedly choose an uncovered element and one set containing it. The resulting cover $J$ satisfies $|J|\le d\mathrm{OPT}$ in polynomial time. The parameter $d$ bounds set size, not element frequency.

Construction

Each selection must cover something new

Maintain the uncovered elements $R$. Choose $u\in R$, choose any $S_j$ containing $u$, select it and remove $S_j$ from $R$. A previously selected set cannot be chosen this way: all its elements are already covered.

Thus every iteration selects one new set and removes at least one new element. There are at most $n=|U|$ iterations, yielding $|J|\le n$.

if union(S[1],...,S[q]) != U: return INFEASIBLE
J = empty set; R = U
while R is nonempty:
    choose u in R
    choose j with u in S[j]
    J.add(j)
    R = R minus S[j]
return J

Approximation guarantee

Compare selections with the number of elements

The algorithm returns a cover of size at most $n$

The loop removes only elements covered by selected sets and ends with no uncovered elements. Each iteration removes its chosen element, so $|J|\le n$.

Any cover needs at least $n/d$ sets

For any feasible index set $K$, the union bound gives
$n=\left|{\bigcup }_{j\in K}{S}_j\right|\le {\sum }_{j\in K}|S_j|\le d|K|.$
Overlap can only reduce the union size. In particular, $n\le d\mathrm{OPT}$.

Combine the bounds

The algorithm pays at most once per element, while an optimal set can account for at most $d$ elements:
$|J|\le n\le d\mathrm{OPT}.$

Running time and scope

With $L={\sum }_j|S_j|$, a straightforward implementation takes $O((n+1)(n+q+L))$ time. An empty universe returns the empty cover; an uncovered-by-all-sets element makes the instance infeasible.

This is a simple $d$-approximation, not a claim of the best possible approximation factor. Unlike the bounded-frequency algorithm, it selects only one set per chosen element and does not need witnesses that avoid sharing input sets.