Uniform Sampling Through the Lovasz Local Lemma

被引：32

作者：

Guo, Heng ^{[1
]}

Jerrum, Mark ^{[2
]}

Liu, Jingcheng ^{[3
]}

机构：

[1] Univ Edinburgh, Sch Informat, Edinburgh EH8 9AB, Midlothian, Scotland

[2] Queen Mary Univ London, Sch Math Sci, London E1 4NS, England

[3] Univ Calif Berkeley, Dept EECS, Berkeley, CA 94720 USA

来源：

JOURNAL OF THE ACM | 2019年 / 66卷 / 03期

基金：

英国工程与自然科学研究理事会;

关键词：

Exact sampling; Lovasz Local Lemma; #SAT; ALGORITHMIC APPROACH;

D O I：

10.1145/3310131

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We propose a new algorithmic framework, called partial rejection sampling, to draw samples exactly from a product distribution, conditioned on none of a number of bad events occurring. Our framework builds new connections between the variable framework of the Lovasz Local Lemma and some classical sampling algorithms such as the cycle-popping algorithm for rooted spanning trees. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences.

引用

页数：31

共 41 条

[1] Random Walks That Find Perfect Objects and the Lovasz Local Lemma [J].

Achlioptas, Dimitris ;

Iliopoulos, Fotis .

JOURNAL OF THE ACM, 2016, 63 (03)

[2] A PARALLEL ALGORITHMIC VERSION OF THE LOCAL LEMMA [J].

ALON, N .

RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (04) :367-378

[3] AN ALGORITHMIC APPROACH TO THE LOVASZ LOCAL LEMMA .1. [J].

BECK, J .

RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (04) :343-365

[4]

Bezakova Ivona, 2016, ICALP, V45, P1

[5]

Bordewich M, 2006, LECT NOTES COMPUT SC, V4051, P108, DOI 10.1007/11786986_11

[6]

Bubley R, 1997, PROCEEDINGS OF THE EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P248

[7]

Czumaj A, 2000, RANDOM STRUCT ALGOR, V17, P213, DOI 10.1002/1098-2418(200010/12)17:3/4<213::AID-RSA3>3.0.CO

[8]

2-Y

[9]

enry Cohn, 2002, C MATH SOC J BOLYAI, V9

[10]

Erds P., 1975, Problems and Results on 3-Chromatic Hypergraphs and Some Related Questions, P609

← 1 2 3 4 5 →