کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952325 | 1364440 | 2017 | 10 صفحه PDF | دانلود رایگان |
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â¥2. Then we show that Max NAE-k-SAT cannot be approximated within 2kâ12kâ1â1 in polynomial time, if Pâ 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.
Journal: Theoretical Computer Science - Volume 657, Part A, 2 January 2017, Pages 54-63