CS294-2 Markov Chain Monte Carlo: Foundations Applications Fall 2002 (2007)
Lecturer Alistair, Sinclair Scribes, Gabor Pete, Sam Riesenfeld
utions to the "0-1 knapsack problem" with n objects with weights a i and knapsack capacity b. Theorem 16.1 For any {a i=1 and b, # mix = O(n 4.5+# ). We will prove a weaker polynomial bound...