|
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 results extend to the case of any xed number of 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. 1, |
