Dealing with 4-variables by resolution: An improved MaxSAT algorithm Academic Article

abstract

• 2017 Elsevier B.V. We study techniques for solving the MAXIMUM SATISFIABILITY problem (MAXSAT). Our focus is on variables of degree 4. We identify cases for degree-4 variables and show how the resolution principle and the kernelization techniques can be nicely integrated to achieve more efficient algorithms for the MAXSAT problem. As a result, we present an algorithm of time O(1.3248k) for the MAXSAT problem, improving the previous best upper bound O(1.358k) by Ivan Bliznets and Alexander Golovnev.

authors

• Chen, Jianer

published proceedings

• THEORETICAL COMPUTER SCIENCE

author list (cited authors)

• Chen, J., Xu, C., & Wang, J.

citation count

• 2

complete list of authors

• Chen, Jianer||Xu, Chao||Wang, Jianxin

publication date

• March 2017

publisher

• Elsevier  Publisher

published in

• Theoretical Computer Science  Journal

keywords

• Branch And Bound
• Maximum Satisfiability
• Parameterized Algorithm
• The Resolution Principle

Digital Object Identifier (DOI)

• 10.1016/j.tcs.2017.01.020

start page

• 33

end page

• 44

volume

• 670

URL

• http://dx.doi.org/10.1016/j.tcs.2017.01.020