Mixing Time of Markov chain of the Knapsack Problem

2018/03/11 by Koko K. Kayibi, Kayibi, Koko K., S. Pirzada +3
Computer Science · Mathematics · #05C99 #11K99 #Algorithms and Data Compression #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1803.06914

openalex publication_date 2018/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 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(ε) ≤ n³ ln (16 ε^-1).

Related

• Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)
• Mixing times are hitting times of large sets
• Faster Mixing of the Jerrum-Sinclair Chain
• Elementary Bounds On Mixing Times for Decomposable Markov Chains
• Mixing Time on the Kagome Lattice