Cover Image

Note on the knapsack Markov chain

We show that for sufficiently large knapsacks the associated Markov chain on the state space of the admissible packings of the knapsack is rapidly mixing. Our condition basically states that at least half of all items should fit into the knapsack. This is much weaker than the condition assumed by Saloff-Coste (1997).
Year of publication:
2001
Authors: Löwe, Matthias ; Meise, Christian
Published in:
Stochastic Processes and their Applications. - Elsevier, ISSN 0304-4149. - Vol. 94.2001, 1, p. 155-170
Publisher: Elsevier
Subject: Markov chains Spectral estimates
Type of publication: Article
Source:
Persistent link: https://www.econbiz.de/10008873027
Similar items by person