๐ฎ
๐ฎ
The Ethereal
Mixing Time of Markov chain of the Knapsack Problem
March 11, 2018 ยท The Ethereal ยท ๐ arXiv.org
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Koko K. Kayibi, S. Pirzada, Carrie Rutherford
arXiv ID
1803.06914
Category
math.CO: Combinatorics
Cross-listed
cs.DS,
math.PR
Citations
0
Venue
arXiv.org
Last Checked
3 months ago
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+ฮต})$, for any $ฮต> 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 $ฯ_{_{x}}(ฮต) \leq n^{3} \ln (16 ฮต^{-1})$.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal