论文部分内容阅读
合取范式可满足与最大可满足问题是理论计算机科学的核心问题.最大不全满足问题是最大可满足问题的一般化.限制每个子句均含有k（≥2）个字母的最大不全满足问题又称为最大不全k满足问题.最大不全满足问题的算法进展,以解答该类问题的半定规划松弛法最具代表性.关于最大不全2满足、3满足和4满足问题,目前性能最好的近似算法分别由Goemans与Williamson、Zwick、Karloff与Zwick给出,近似性能比分别为1.139（1/0.878）、1.10047（1/0.9087）和8/7.当k≥5时,最大不全k