Generating a Random Linear Extension of a Partial Order
Author:
- Peter MatthewsPMPeter Matthews
Open Access
- 1 July 1991
- journal article
- research article
- Published by Institute of Mathematical Statistics in The Annals of Probability
- Vol. 19 (3) , 1367-1392
Abstract
Given a partial order of $N$ items, a linear extension that is almost uniformly distributed, in the sense of variation distance, is generated. The algorithm runs in polynomial time. The technique used is a coupling for a random walk on a polygonal subset of the unit sphere in $\mathbb{R}^N$. Including is a discussion of how accurately the steps of the random walk must be computed.