First, alg:basic-nonmono further sub-samples the elements of the input so that the probability of including any element is exactly \(1/(\alpha k)\)  lines – (coloured in  orange). The sub-sampling allows us to bound the maximum probability that an element of the input is included in the solution. In particular, the sub-sampling is done by having the algorithm compute (on the fly) the conditional probability that an element \(e\)  could have been selected had it appeared in the past. This gives us the ability to compute an appropriate sub-sampling probability to ensure that \(e\)  does not appear in \(H\)  with too high a probability. In terms of the proof, the sub-sampling allows us to perform a similar analysis to the RandomGreedy algorithm of Buchbinder et al. [1]}.A difference here is that instead of analysing a random element of the top-\(k\)  marginals, we analyse the optimal set directly.
