Note on the knapsack Markov chain.
From MaRDI portal
In the knapsack problem, admissible packings \((x_1,\dots ,x_n)\in\! \{0,1\}^n\) are defined by \({\sum \limits_{i=1}^na_ix_i\leq b}\) where \(a_1,\dots ,a_n,b\) are given positive integers. On the assumption that each packing with at most \(\alpha n\) one's is admissible, \(1/2<\alpha \leq 1\), a Markov chain on the set of admissible packings is shown to be rapidly mixing. This follows from a new lower bound on the spectral gap \(1-\beta _1\) where \(\beta _1\) is the second largest eigenvalue of the transition matrix.
Recommendations
Cites work
- Application of coupling method to the first eigenvalue on manifold
- Estimation of spectral gap for Markov chains
- Geometric bounds for eigenvalues of Markov chains
- scientific article; zbMATH DE number 1069282 (Why is no real title available?)
- Matrix Analysis
- Random generation of combinatorial structures from a uniform distribution
- Walks on generating sets of Abelian groups
Cited in
(2)
This page was built for publication: Note on the knapsack Markov chain.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1888773)
