A polynomial time Monte-Carlo algorithm which produce a good approximation solution to an enumeration problem for which it is known that the computation of the exact solution is very hard.
DNF coungting (#P-complete)
GOAL: to count the number of truth assignments which satisfy the disjunctive normal form.
A $\varepsilon, \delta$-approximation algorithm satitifies that
We have a finite set $U$ and a function $f$ defined on $U$ such that $f(u) = 1$ if and only if $u$ is one of the truth assignments.
Our goal is to estimate $|G|$, where $G = \{u \mid f(u) = 1, u \in U\}$.
- A simple method
choose $u \in U$ randomly, compute $f(u)$, and set $Y \gets |U|\times f(u)$, return $\tilde{Y} = \sum^N_{i = 1}Y_i/N$.
$E[Y] = |G|$, and $E[\tilde{Y}] = |G|$. Then, we need to bound $N$.
Zero-One Estimator Theorm Let $\mu = |G|/|U|$. Let $\varepsilon \le 2$. If $N \ge (1/\mu)\cdot(4\ln{(2/\delta)}/\varepsilon^2)$ then the algorithm is an $\varepsilon, \delta$-approximation algorithm.
However, $|U|/|G|$ can not be bound in the above procedure.
Luby-Karp Algorithm
A general set problem: given $m$ sets $G1, \cdots, G_m$, the goal is to compute $|G|$, where $G = \bigcup_{i = 1}^m G_i$. Let $U = G_1\oplus\cdots\oplus G_m $, i.e., each element in $U$ is represented by $(s, i)$, where $s \in G_i$. $|U| = \sum^m_{i = 1}|G_i|$. Define $f(s, i) = 1$ if $i$ is the smallest index such that $s \in G_i$. Note that $|G| = \sum_{(s, i) \in U}f(s, i)$.
The algorithm runs as follows:- choose $i \in \{1, \cdots, m\}$ with probability $|G_i|/|U|$.
- choose $s \in G_i$ with probability $1/|G_i|$.
- compute $Y \gets f(s, i)\cdot |U|$.
$E[Y] = |G|$, and $E[\tilde{Y}] = |G|$. The most important thing is that $m \ge 1/\mu = |U|/|G|$. Thus, $N$ is bounded by $O(m\cdot\ln{(2/\delta)}/\varepsilon^2)$.