Math @ Duke

Publications [#47822] of Mark Huber
Papers Published
 Mark L. Huber, Fast perfect sampling from linear extensions,
Discrete Mathematics, vol. 306
(2006),
pp. 420428, Elsevier
(last updated on 2006/12/18)
Abstract: In this paper we study the problem of
sampling (exactly) uniformly from the set of
linear extensions of an arbitrary partial
order. Previous Markov chain techniques have
yielded algorithms that generate
approximately uniform samples. Here we
create a bounding chain for one such Markov
chain, and by using a nonMarkovian coupling
together with a modified form of coupling
from the past, we build an algorithm for
perfectly generating samples. The expected
running time of the procedure is $O(n^3 \ln
n)$, making the technique as fast than the
mixing time of the Karzanov/Khachiyan chain
upon which it is based.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

