Mixing Time of Markov chain of the Knapsack Problem

Authors K. K. Kayibi, Shariefuddin Pirzada, Carrie Rutherford

Publication date 11 March 2018

Graph theory (05C99) Probabilistic theory: distribution modulo (1); metric theory of algorithms (11K99)

Abstract: To find the number of assignments of zeros and ones satisfying a specific Knapsack Problem is

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

m a t h c a l O (n^{9 / 2 + e p s i l o n})

, for any

e p s i l o n > 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

a u_{_{x}} (e p s i l o n) l e q n^{3} l n (16 e p s i l o n^{- 1})

.

This page was built for publication: Mixing Time of Markov chain of the Knapsack Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6299242)