cover.set_cover_rr(subsets, weights=None, maxiter=None, sparsity=1.0, seed=None)
Approximates the weighted set cover problem via randomized rounding.
This function first computes a minimum-cost fractional set cover whose solution lower-bounds the optimal solution, then uses randomized rounding to produce a sequence of solutions whose objectives slightly increase this bound, continuing until a feasible solution is found.
The minimum-cost fractional cover is obtained by solving the following linear program:
\[\begin{align*}\text{minimize} \quad & \sum\limits_{j \in [J]} s_j \cdot w_j \\ \text{s.t.} \quad & \sum\limits_{j \in N_i} s_j \geq 1, \quad \forall \, i \in [n] \\ & s_j \in [0, 1], \quad \forall \, j \in [J]\end{align*}\]
where \(s_j \in [0, 1]\) is a real number indicating the strength of the membership \(S_j \in \mathcal{S}\) and \(N_i\) represents the subsets of \(S\) that the element \(x_i\) intersects. The randomized rounding procedure iteratively adds sets \(S_j\) with probability \(c \cdot s_j\) until a feasible cover is found.
If not supplied, maxiter defaults to \((2 / c) \log(n)\) where \(c\) is given by the sparsity argument. Supplying sparsity values lower than 1 allows choosing fewer subsets per iteration, which can result in sparser or lower weight covers at the cost of more iterations.
| 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 |
maxiter |
Optional[int] | number of iterations to repeat the sampling process. See details. | None |
sparsity |
float | constant used to emphasize sparsity between (0, 1]. See details. | 1.0 |
seed |
Optional[int] | seed for the random number generator. Use an integer for deterministic computation. | None |
| Type | Description |
|---|---|
| tuple | pair (s, c) where s is an array indicating cover membership and c its cost. |
Sparse arraysThis function requires subsets to be a sparse matrix in canonical CSC form.
If subsets is not in this form, a copy of the subsets is converted first; to avoid this for maximum performance, ensure the subset matrix is in canonical form first.
from geomcover.cover import set_cover_rr
from geomcover.io import load_set_cover
subsets, weights = load_set_cover("mushroom")
soln, cost = set_cover_rr(subsets, weights)
n, J = subsets.shape
print("Set family with {n} elements and {J} sets can be covered with {np.sum(soln)} sets with cost {cost}.")Set family with {n} elements and {J} sets can be covered with {np.sum(soln)} sets with cost {cost}.