Name
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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1137/S0097539702411915 | SIAM Journal on Computing |
Keywords | Field | DocType |
symmetric random walk,open problem,uniform permutation,random walks,knapsack solutions,combinatorial construction,fixed number,feasible solution,polynomial randomized approximation scheme,key ingredient,knapsack problem,truncated cubes,independent interest,n-dimensional cube,fully-polynomial randomized approximation scheme,machinery,mixing time,sampling,approximation theory,approximation algorithms,sampling methods,computational complexity,hyperplane,multicommodity flow,statistics,markov chains,computer science | Discrete mathematics,Approximation algorithm,Combinatorics,Open problem,Random walk,Permutation,Continuous knapsack problem,Knapsack problem,Multi-commodity flow problem,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
34 | 1 | 0097-5397 |
ISBN | Citations | PageRank |
0-7695-0409-4 | 38 | 2.14 |
References | Authors | |
6 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ben Morris | 1 | 127 | 8.78 |
| Alistair Sinclair | 2 | 1506 | 308.40 |