Improved exact algorithms for MAX-SAT Conference Paper

abstract

• Springer-Verlag Berlin Heidelberg 2002. 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.3247^m|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.3695^k k² + |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.

name of conference

• LATIN 2002: Theoretical Informatics, 5th Latin American Symposium, Cancun, Mexico, April 3-6, 2002, Proceedings

authors

• Chen, Jianer

published proceedings

• LATIN 2002: THEORETICAL INFORMATICS

author list (cited authors)

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

citation count

• 11

complete list of authors

• Chen, J||Kanj, IA

publication date

• January 2002

publisher

• Springer Nature  Publisher

published in

• Lecture Notes in Artificial Intelligence  Journal

keywords

• Exact Algorithms
• Maximum Satisfiability
• Parameterized Algorithms

Digital Object Identifier (DOI)

• 10.1007/3-540-45995-2_32

International Standard Book Number (ISBN) 10

• 3-540-43400-3

International Standard Book Number (ISBN) 13

• 9783540434009

start page

• 341

end page

• 355

volume

• 2286

URL

• http%3A%2F%2Fdx.doi.org%2F10.1007%2F3-540-45995-2_32