Robin Moser makes Lovász Local Lemma Algorithmic ! Notes of
Robin Moser makes Lovász Local Lemma Algorithmic ! Notes of
复制标题
Robin Moser 制作 Lovasz 局部引理算法笔记！
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
J. Spencer
中科院分区：
文献类型：
--
作者：
J. Spencer
这些笔记中的想法是解释Robin Moser 1给出Lovász局部引理算法的一种新方法。本文描述的是Gábor Tardos修改和改进的方法。我们不追求最好的可能或最普遍的。特别地，我们坚持所谓的对称情况。让我们从一个特殊的、有启发性的例子开始。设xi， 1≤i≤n为布尔变量。设Cj， 1≤j≤m为子句，每个子句表示k个变量的析取或它们的负值。例如，当k = 3时，x8∨x19∨x37就是一个典型的子句。假设两个子句重叠，写下Ci ~ Cj，如果它们有共同变量xk，不管子句中变量是否为负。如果一组子句存在一个底层变量的真值赋值，使得每个子句都是满足的，或者，等价地，如果子句的∧是可满足的，则称为一组子句是可互满足的。
The idea in these notes is to explain a new approach of Robin Moser 1 to give an algorithm for the Lovász Local Lemma. This description is of the approach as modified and improved by Gábor Tardos. We don’t strive for best possible or most general here. In particular, we stick to what is called the symmetric case. Lets start with a particular and instructive example. Let xi, 1 ≤ i ≤ n be Boolean variables. Let Cj, 1 ≤ j ≤ m be clauses, each the disjunction of k variables or their negations. For example, with k = 3, x8∨x19∨x37 would be a typical clause. We say two clauses overlap, and write Ci ∼ Cj, if they have a common variable xk, regardless of whether the variable is negated or not in the clauses. A set of clauses is called mutually satisfiable if there exists a truth assignment of the underlying variables so that each clause is satisfied or, equivalently, if the ∧ of the clauses is satisfiable.