کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651389 | 1342540 | 2006 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fast perfect sampling from linear extensions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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(n3lnn)O(n3lnn), making the technique as fast as the mixing time of the Karzanov/Khachiyan chain upon which it is based.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issue 4, 6 March 2006, Pages 420–428
Journal: Discrete Mathematics - Volume 306, Issue 4, 6 March 2006, Pages 420–428
نویسندگان
Mark Huber,