Approximate Counting by Dynamic Programming
  Martin E. Dyer

Abstract:

We will outline an efficient algorithm to sample uniformly, and count
approximately, the number solutions to a zero-one knapsack problem. The
previous approach to this problem was based on ``Markov chain Monte
Carlo''. The new algorithm uses dynamic programming to provide a
deterministic relative approximation. Then a simple ``dart throwing''
technique is used to give an arbitrary approximation ratio. We will
indicate a further improvement using randomized rounding.