Mark Huber Publications

Fast perfect sampling from linear extensions
M. L. Huber, Discrete Mathematics, vol. 306 (2006), pp. 420428.

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 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(n3 ln n), making the technique as fast as the mixing time of the Karzanov/Khachiyan chain upon which it is based.

Keywords: MCMC; Perfect simulation; Linear extensions

This site supported by NSF CAREER grant DMS-05-48153. Last update: 04 December 2009. Note: All downloads provided solely for use within the restrictions of the Fair Use Act, and all copyrights remain with their respective owners.