Note on the knapsack Markov chain

M. Löwe, C. Meise

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    1 Citaat (Scopus)
    1 Downloads (Pure)

    Samenvatting

    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).
    Originele taal-2Engels
    Pagina's (van-tot)155-170
    TijdschriftStochastic Processes and their Applications
    Volume94
    Nummer van het tijdschrift1
    DOI's
    StatusGepubliceerd - 2001

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Note on the knapsack Markov chain'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit