Approximating Max NAE-k-SAT by anonymous local search

详细信息    查看全文

• 作者：Aiyong Xian^a ; Kaiyuan Zhu^b ; Daming Zhu^a ; ^{dmzhu@sdu.edu.cn} ; Lianrong Pu^a ; Hong Liu^a
• 关键词：Local search ; Algorithm ; Complexity ; Performance ratio ; Satisfiability
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：2 January 2017
• 年：2017
• 卷：657
• 期：part_PA
• 页码：54-63
• 全文大小：339 K
• 卷排序：657

文摘

A clause is not-all-equal satisfied if it has at least one literal assigned with true and one literal assigned with false. Max NAE-SAT is given by a boolean variable set U and a clause set C, asks to find an assignment of U, such that the number of not-all-equal satisfied clauses in C is maximized. Max NAE-SAT turns into Max NAE-k-SAT if each clause contains exactly k literals. Local search has long been used in various SAT solvers. However, little has been done on local search to approximate Max NAE-k-SAT. Moreover, it is still open for what a quantitative bound could Max NAE-k-SAT be approximated to, at best. In this paper, we propose a local search algorithm which can approximate Max NAE-k  -SAT to 2k−12k−1−1 for each fixed k≥2k≥2. Then we show that Max NAE-k  -SAT cannot be approximated within 2k−12k−1−1 in polynomial time, if P≠NPP≠NP. The algorithm for Max NAE-k-SAT can be extended to approximate Max NAE-SAT where each clause contains at least k   literals to 2k−12k−1−1. Using the algorithm for Max NAE-SAT where each clause contains at least k literals, we present a new algorithm to approximate Max-SAT where each clause contains at least k   literals to 2k2k−1.