Balanced max 2-sat might not be the hardest
Balanced max 2-sat might not be the hardest
复制标题
平衡最大 2-sat 可能不是最难的
DOI：
10.1145/1250790.1250818
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Per Austrin
中科院分区：
文献类型：
--
作者：
Per Austrin
我们表明，假设唯一的游戏猜想，它是np-hard在αllz-+ε内的近似max2sat，其中0.9401 <αllz-<0.9402是Lewin，Livnat和Zwick [28]的据信据信的近似值。
考虑到Max2sat的平衡实例，即每个变量的正常和负相同发生，尤其是在0.9439之内，大约有68％的文字是未隔离的变量和32％的实例，这一结果令人惊讶。与比率为50％-50％的情况相比，被否定的外观不适合近似。
We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate MAX2SAT within αLLZ-+ε, where 0.9401 < αLLZ- < 0.9402 is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick [28].
This result is surprising considering the fact that balanced instances of MAX2SAT, i.e., instances where each variable occurs positively and negatively equally often, can be approximated within 0.9439. In particular, instances in which roughly 68% of the literals are unnegated variables and 32% are negated appear less amenable to approximation than instances where the ratio is 50% - 50%.