- Repeat until all elements of $U$ are covered - Pick the set $S_i$ with the largest number of uncovered elements - let $J$ be the set of subsets chosen for the output, that covers all elements - note there are $n$ elements - Claim: - $|J| \leq |J^*|\,ln(n)$ - (our greedy solution will only at most be $ln(n)$ times as bad as the optimal solution, will not stray any farther up) ![[CleanShot 2024-05-09 at 11.49.38.png|400x200]] - let $n_t$ be the number of uncovered points after $t$ greedy iterations - meaning $n_0$ = $n$ - note the below formula, least amount you can subtract each time is $\frac{n_t}{|J^*|}$ cause after $|J^*|$ iterations you end up with nothing - $n_{t+1} \leq n_t - \frac{n_t}{|J^*|} = n_t \left(1 - \frac{1}{|J^*|}\right)$ - $n_t \leq n_0 \left(1 - \frac{1}{|J^*|}\right)^t$