Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#47822] of Mark Huber

Papers Published

  1. Mark L. Huber, Fast perfect sampling from linear extensions, Discrete Mathematics, vol. 306 (2006), pp. 420--428, Elsevier
    (last updated on 2006/12/18)

    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 non-Markovian 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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320