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.