Approximately Counting Knapsack Solutions

Photograph of Martin Dyer

Martin Dyer


We will describe an algorithm for approximating the number of solutions to a zero-one knapsack inequality. The talk will be self-contained, since we will first review the relevant computational ideas of exact and approximate counting.
Tuesday 28th June 2005, 14:00
Robert Recorde Room
Department of Computer Science