Personal tools
You are here: Home Events Abstract Archives 2003 Approximate Counting by Dynamic Programming

Approximate Counting by Dynamic Programming

Martin Dyer School of Computing University of Leeds 4pm Tuesday 27 May 2003 Room 2511, JCMB, King's Buildings

We will describe an efficient algorithm to sample uniformly, and count approximately, the 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 outline a further improvement using randomized rounding. The approach extends to some related problems: the multidimensional zero-one knapsack, the general integer knapsack and contingency tables with constantly many rows.

Document Actions