The University of Michigan Combinatorics Seminar
Winter 2002
January 11, 4:10-5:00, 3866 East Hall

Random Walks on Truncated Cubes and Sampling Knapsack Solutions

Ben Morris

University of California at Berkeley


We solve an open problem concerning the mixing time of symmetric random walk on the n-dimensional cube truncated by a hyperplane, showing that it is polynomial in n. As a consequence, we obtain a fully-polynomial randomized approximation scheme for counting the feasible solutions of a 0-1 knapsack problem. We also generalize to any fixed number of knapsack constraints (hyperplanes). The key ingredient in our analysis is a combinatorial construction we call a "balanced almost uniform permutation," which seems to be of independent interest. This is joint work with Alistair Sinclair.