Bounded-Frequency Set Cover Approximation Algorithm

Definition

Bounded-Frequency Set Cover Approximation Algorithm

For a feasible Minimum Set Cover instance, let
$d={\max }_{u\in U}|\{j:u\in S_j\}|.$
Repeatedly choose an uncovered element and select all sets containing it. For nonempty $U$, this polynomial-time algorithm returns a cover $J$ satisfying $|J|\le d\mathrm{OPT}$. The parameter $d$ bounds element frequency, not set size.

Construction

Select every occurrence of an uncovered element

Let $R$ be the uncovered elements and $J$ the selected set indices. For a chosen $u\in R$, define $O(u)=\{j:u\in S_j\}$, add all of $O(u)$ to $J$, and remove ${\bigcup }_{j\in O(u)}{S}_j$ from $R$.

Selecting all occurrences is essential: any element sharing any input set with $u$ becomes covered immediately. Record each chosen element as a witness in $W$.

Pseudocode

if union(S[1],...,S[q]) != U: return INFEASIBLE
J = empty set; W = empty set; R = U
while R is nonempty:
    choose u in R
    W.add(u)
    O = {j : u belongs to S[j]}
    J = J union O
    R = R minus union(S[j] for j in O)
return J

Approximation guarantee

Witnesses bound the optimum from below

Feasibility and cost per witness

Every iteration covers its chosen element, so the algorithm terminates with a cover. At most $d$ sets are added per witness:
$|J|\le {\sum }_{u\in W}|O(u)|\le d|W|.$

An input set cannot contain two witnesses

Suppose $u$ is chosen before $v$ and both lie in $S_j$. When $u$ is chosen, $j\in O(u)$, so every element of $S_j$, including $v$, becomes covered. Then $v$ cannot be chosen later from $R$, a contradiction. Thus $|S_j\cap W|\le 1$ for every input set.

Every cover must pay once per witness

Every cover covers all of $W$, but each selected set covers at most one witness. Hence $\mathrm{OPT}\ge |W|$. Combining the two counts gives
$|J|\le d|W|\le d\mathrm{OPT}.$

Running time and boundary cases

Write $n=|U|$, $q$ for the number of sets and $L={\sum }_j|S_j|$. A direct implementation scans the incidence lists in each of at most $n$ iterations, taking $O((n+1)(n+q+L))$ time. If $U$ is empty, return the empty cover without defining a maximum frequency. If an element belongs to no input set, report infeasibility before the loop.

The bounded-set-size algorithm has a different lower-bound argument: limiting the number of elements per set is not the same as limiting the number of sets per element.