Faster random generation of linear extensions (Q1301730)

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.