I will present the main result of Martin Dyer's STOC'03
paper "Approximate Counting by Dynamic Programming". In it, Dyer considers the
problem of counting the number of solutions to a knapsack problem, a
#P-complete problem. The first randomized approximation scheme for
the problem was developed in 1993 by Dyer et. al. Unfortunately, its
running time was 2^{\Omega{\sqrt{n}}. In a 1999 breakthrough,
Morris and Sinclair developed an "fpras" for
the problem, with running time O(n^{9/2 + \epsilon}). Both algorithms use the
Markov Chain Monte Carlo (MCMC) approach to do
approximate counting through approximate uniform sampling.
Dyer's 2003 O(n^3 + n^2/\epsilon^2) algorithm doesn't use the MCMC
approach. Instead, he develops a O(n^3) dynamic
programming computation with a deterministic
approximation ratio. Then, he uses a simple "dart throwing" technique to make
the ratio arbitrarily small.
The paper is available at: http://www.comp.leeds.ac.uk/dyer/stoc03.pdf