pith. sign in

arxiv: 1803.06914 · v1 · pith:5V5Q7QRKnew · submitted 2018-03-11 · 🧮 math.CO · cs.DS· math.PR

Mixing Time of Markov chain of the Knapsack Problem

classification 🧮 math.CO cs.DSmath.PR
keywords epsilonchainmarkovmixingtimeargumentgivenknapsack
0
0 comments X
read the original abstract

To find the number of assignments of zeros and ones satisfying a specific Knapsack Problem is $\#P$ hard, so only approximations are envisageable. A Markov chain allowing uniform sampling of all possible solutions is given by Luby, Randall and Sinclair. In 2005, Morris and Sinclair, by using a flow argument, have shown that the mixing time of this Markov chain is $\mathcal{O}(n^{9/2+\epsilon})$, for any $\epsilon > 0$. By using a canonical path argument on the distributive lattice structure of the set of solutions, we obtain an improved bound, the mixing time is given as $\tau_{_{x}}(\epsilon) \leq n^{3} \ln (16 \epsilon^{-1})$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.