cover.set_cover_greedy
cover.set_cover_greedy(subsets, weights=None)
Approximates the weighted set cover problem via greedy steps.
This function iteratively constructs a set cover \(\mathcal{C} \subseteq \mathcal{S}\) by choosing the set that covers the largest number of uncovered elements with the least weight:
\[ \min_{S_i \in \mathcal{S}} \; w_i \, / \, \lvert S_i \cap \mathcal{C}' \rvert, \quad \mathcal{C}' = U \setminus \mathcal{C} \]
It has been shown that the algorithm has a worst-case multiplicative \(\log(n + 1)\)-approximation factor [1]. The greedy strategy is a very fast SC algorithm, though counter-examples have demonstrated the method can produce poor covers on certain pathological inputs.
Parameters
| Name | Type | Description | Default |
|---|---|---|---|
subsets |
sparray | (n x J) sparse matrix of J subsets whose union forms a cover over n points. |
required |
weights |
Optional[ArrayLike] | (J)-length array of subset weights. | None |
Returns
| Type | Description |
|---|---|
| tuple | pair (s, c) where s is an array indicating cover membership and c its cost. |
Notes
The algorithm implemented here uses the ‘dual-fitting’ variant discussed in 5.3 of [2] below, which
can be used used to generate a feasible solution to dual LP.
References
- Feige, Uriel. “A threshold of ln n for approximating set cover.” Journal of the ACM (JACM) 45.4 (1998): 634-652.
- CS 583 notes by Chandra Chekuri