Random Instance Generation for MAX 3SAT
Random Instance Generation for MAX 3SAT
复制标题
MAX 3SAT 的随机实例生成
DOI：
10.1007/3-540-44679-6_56
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Mitsuo Motoki
中科院分区：
文献类型：
--
作者：
Mitsuo Motoki
MAX SAT是著名的组合优化问题之一，其表述如下：给定一个多子句集，找到一个使满足子句的数目最大化的分配（这等价于找到一个使不满足子句的数目最小化的分配）。MAX 3SAT是MAX SAT的受限版本，也就是说，它的输入被限制为3-子句的多集，即，每个子句包含正好3个字面值，其基础变量彼此不同。由于这些问题不仅是NP难问题，而且是MAX SNP完全问题，因此除非P = NP，否则没有多项式时间近似算法的近似比接近1。此外，Håstad证明了对于任何eε > 0，在8/7 - ε内近似MAX 3SAT是NP困难的[5]。尽管有这些负面的结果，许多多项式时间近似算法已被证明近似比MAX SAT提出[3，4，7]。
MAX SAT is one of famous combinatorial optimization problems stated as follows: given a multiset of clauses, find an assignment that maximizes the number of satisfied clauses (that is equivalent to finding an assignment that minimizes the number of unsatisfied clauses). MAX 3SAT is restricted version of MAX SAT, that is, its input is restricted to a multiset of 3-clauses, i.e., each clause contains exactly 3 literals whose underlying variables are distinct each other. Since these problems are not only NP-hard problem, but MAX SNP-complete problem, there is no polynomial time approximation algorithm whose approximation ratio is close to 1 unless P = NP. Furthermore, Håstad showed that it is NP-hard to approximate MAX 3SAT within 8/7 - ε for any eε > 0 [5]. In spite of these negative results, many polynomial time approximation algorithms with proven approximation ratio for MAX SAT have been proposed [3,4,7].