Sinclair
Le Jeudi 15 Mars 2001 à 16h00
au LRI, Salle 101
(Computer Science Division, UC Berkeley)
Random walks on truncated cubes and sampling knapsack solutions
Résumé/Abstract :
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. The key ingredient
in our analysis is a combinatorial construction we call a "balanced
almost uniform permutation," which seems to be of independent interest.
The result extends to truncation by any fixed number of hyperplanes.
(This is joint work with Ben Morris.)