Karp-Luby sampling

[make-github-pseudonymous-again]

Linear time measure approximation of a set union given oracles for uniform sampling on the multiset union and membership testing on the insertion-order labeled set union.

measure: |S| e.g. volume, cardinality, ...

set union: U_i S_i

uniform sampling on the multiset union: Sample (y, k) from U_i { (x, i) : x in S_i } uniformly at random.

membership testing on the union-order labeled set union: Test whether (y, k) belongs to U_i { (x, i) : x in S_i, x not in S_j for j < i }. Can be implemented as testing whether y belongs to { x in S_k : x not in S_j for j < k } in general.

References

• 1983 Karp, Luby Monte-Carlo algorithms for enumeration and reliability problems
• 1989 Karp, Luby, Madras Monte-Carlo approximation algorithms for enumeration problems