Note on the knapsack Markov chain

M. Löwe, C. Meise

    Research output: Contribution to journalArticleAcademicpeer-review

    1 Citation (Scopus)
    1 Downloads (Pure)

    Abstract

    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).
    Original languageEnglish
    Pages (from-to)155-170
    JournalStochastic Processes and their Applications
    Volume94
    Issue number1
    DOIs
    Publication statusPublished - 2001

    Fingerprint

    Dive into the research topics of 'Note on the knapsack Markov chain'. Together they form a unique fingerprint.

    Cite this