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.
Publié le : 1991-07-14
Classification:
Random walk,
coupling,
uniform generation,
volume of a polyhedron,
60B10,
60J15,
06A10
@article{1176990349,
author = {Matthews, Peter},
title = {Generating a Random Linear Extension of a Partial Order},
journal = {Ann. Probab.},
volume = {19},
number = {4},
year = {1991},
pages = { 1367-1392},
language = {en},
url = {http://dml.mathdoc.fr/item/1176990349}
}
Matthews, Peter. Generating a Random Linear Extension of a Partial Order. Ann. Probab., Tome 19 (1991) no. 4, pp. 1367-1392. http://gdmltest.u-ga.fr/item/1176990349/