| CS294-2 Markov Chain Monte Carlo: Foundations Applications Fall 2002 (2007) | |||||||||||||||
Abstract | |||||||||||||||
| 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 here, by constructing a multicommodity flow with low cost #(f) and small length l(f ). We will look at the vertices x as subsets of {1, . . . , n}, i.e. x # {i : x i = 1}, and we will denote the symmetric di#erence of two sets by x y. Note that the shortest paths between x and y are just the permutations of the set x y. Since we have lost the symmetries of the complete hypercube, we cannot simply route flow uniformly and claim that all edges are equally loaded. Moreover, it seems very hard (if not impossible) to design a reasonable deterministic rule that assigns one particular flow-carrying path to each pair of vertices x, y, as we did with the left-right bit-fixing paths for the full hypercube. What we would like to do is to spread the x more-or-less randomly among all shortes | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||