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

摘要：

合取范式可满足与最大可满足问题是理论计算机科学的核心问题．最大不全满足问题是最大可满足问题的一般化．限制每个子句均含有 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 满足问题的算法近似性能比是最优的．

关键词：局部搜索、算法、近似性能比、合取范式、可满足性

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61070019;教育部博士点基金20090131110009;山东省自然科学基金ZR2012FZ002资助．

在线出版日期：2015-09-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共13页

页码：1561-1573