Faster random generation of linear extensions
type: Item
instance of: scholarly article
title: Faster random generation of linear extensions
zbMATH Open document ID: 0934.65005
DOI: 10.1016/S0012-365X(98)00333-1
author: Russ Bubley
author: Martin Dyer
published in: Discrete Mathematics
publication date: 2000-04-27T00:00:00Z
review text: The paper investigates the problem of sampling (almost) uniformly from the set of linear extensions of a partial order, a classical problem in the theory of approximate sampling. The paper introduces a slightly different notion of Markov chain and provides a simple, non-geometric proof of rapid mixing of a Markov chain employing the authors' previously defined method called path coupling [Path coupling: a technique for proving rapid mixing in Markov chains Proc. 38th Ann. Symp. on Foundations of Computer Science, Miami Beach, Florida, 20-22 Oct., 223-231 (1997)]. The family of the introduced Markov chains includes the Karzanov-Khachiyan chains as a special case [cf. \textit{A. Karzanov} and \textit{L. Khachiyan}, Order 8, No. 1, 7-15 (1991; Zbl 0736.06002)], and the new Markov chain is proved to have the mixing time \(O(n^3\log n)\), which significantly improves the best bound of \(O(n^5\log n)\) for the Karzanov-Khachiyan chain.
reviewed by: Neculai Curteanu
Mathematics Subject Classification ID: 65C40
Mathematics Subject Classification ID: 62D05
Mathematics Subject Classification ID: 60J25
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 62M05
zbMATH DE Number: 1334539
zbMATH Keywords: random generation of linear extensions
zbMATH Keywords: theory of approximate sampling
zbMATH Keywords: almost uniform sampling
zbMATH Keywords: Markov chains
zbMATH Keywords: Karzanov-Khachiyan chains
Wikidata QID: Q29303267
MaRDI profile type: Publication
cites work: Q3660628
cites work: Counting linear extensions
cites work: Generating a random permutation with random transpositions
cites work: Q4153936
cites work: Q3976408
cites work: A random polynomial-time algorithm for approximating the volume of convex bodies
cites work: On Markov Chains for Independent Sets
cites work: Q5501801
cites work: On the conductance of order Markov chains
cites work: Generating a random linear extension of a partial order
cites work: Exact sampling with coupled Markov chains and applications to statistical mechanics
cites work: Generating Linear Extensions Fast
cites work: Approximate counting, uniform generation and rapidly mixing Markov chains
DBLP publication ID: journals/dm/BubleyD99
description: scientific article; zbMATH DE number 1334539