最大不全k满足问题的局部搜索近似算法

The Local Search Approximation Algorithms for Maximum Not-All-Equal k-Satisfiability Problems

合取范式可满足与最大可满足问题是理论计算机科学的核心问题.最大不全满足问题是最大可满足问题的一般化.限制每个子句均含有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满足问题的近似算法则未曾见到.文中给出了一个解答最大不全k满足问题的局部搜索算法,近似性能比可达到2k-1/(2k-1-1),k≥2;进一步将该方法推广到解答由不少于k个字母的子句构成的最大不全k满足问题,近似性能比亦可达到2k-1/(2k-1-1).利用解答最大不全k满足问题的近似算法,给出了解答最大k可满足问题的新近似算法,近似性能比可达到2k/(2k-1).文中最后证明了若P≠NP,则k≥4的最大不全k满足问题不能近似到小于2k-1/(2k-1-1),从而说明文中解答最大不全k满足问题的算法近似性能比是最优的.

The satisfiability problem as well as the maximum satisfiability problem of conjunctive norm forms are the central problems in theoretical computer science.The maximum not-all-equal satisfiability problem is a generalization of the maximum satisfiability problem.The maximum not-all-equal satisfiability problem is named maximum not-all-equal k satisfiability problem,if each clause of its instance contains k（≥2）literals.Semi-definite programming relaxation is the frequently-used also the most typical method for solving the maximum not-all-equal satisfiability problems.To our knowledge at present,the best algorithms for the maximum not-all-equal 2,3and 4satisfiability problems come from the semi-definite programming relaxation methods given by Goemans and Williamson,Zwick,Karloff and Zwick,with performances 1.139（1/0.878）,1.100 47（1/0.9087）and 8/7respectively.When k≥5,we have not seen any approximation algorithm for the maximum not-all-equal ksatisfiability problems.In this paper,we propose a local search algorithm to solve the maximum not-all-equal ksatisfiability problem.This algorithm can achieve the performance ratio 2k-1/（2k-1-1）for k≥2.We extend the method to propose a local search algorithm to solve the more generalized version of the maximum not-all-equal k satisfiability problem,with each clause containing at least k literals.This algorithm can still achieve theperformance ratio 2k-1/（2k-1-1）.Using the method for the generalized version of the maximum not-all-equal ksatisfiability problem,we propose a new 2k/（2k-1）-approximation algorithm for generalized version of the maximumk satisfiability problem.Finally,we prove that if P≠NP,then the maximum not-all-equal k satisfiability problem cannot be approximated within 2k-1/（2k-1-1）for k≥4.This implies the performance ratio of our algorithm for the maximum not-all-equal ksatisfiability problem is optimal.