Improved exact algorithms for MAX-SAT Academic Article uri icon

abstract

  • In this paper, we present improved exact and parameterized algorithms for the maximum satisfiability problem. In particular, we give an algorithm that computes a truth assignment for a boolean formula F satisfying the maximum number of clauses in time O(1.3247m|F|), where m is the number of clauses in F, and |F| is the sum of the number of literals appearing in each clause in F. Moreover, given a parameter k, we give an O(1.3695k+|F|) parameterized algorithm that decides whether a truth assignment for F satisfying at least k clauses exists. Both algorithms improve the previous best algorithms by Bansal and Raman for the problem. 2004 Elsevier B.V. All rights reserved.

published proceedings

  • Discrete Applied Mathematics

author list (cited authors)

  • Chen, J., & Kanj, I. A.

citation count

  • 47

complete list of authors

  • Chen, Jianer||Kanj, Iyad A

publication date

  • August 2004