# zbMATH — the first resource for mathematics

Upper bounds for MaxSat: Further improved. (English) Zbl 0971.68069
Aggarwal, Alok (ed.) et al., Algorithms and computation. 10th international symposium, ISAAC’ 99, Chennai, India, December 16-18, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1741, 247-258 (1999).
Summary: Given a Boolean CNF formula $$F$$ of length $$|F|$$ (sum of the number of variables in each clause) with $$m$$ clauses on $$n$$ variables, we prove the following results:
1) The MAXSAT problem, which asks for an assignment satisfying the maximum number of clauses of $$F$$, can be solved in $$O(1.341294^m|F|)$$ time.
2) The parameterized version of the problem, that is determining whether there exists an assignment satisfying at least $$k$$ clauses of the formula (for some integer $$k$$), can be solved in $$O(k^21.380278^k+|F|)$$ time.
3) MAXSAT can be solved in $$O(1.105729^{|F|}|F|)$$ time.
These bounds improve the recent bounds of respectively $$O(1.3972^m|F|)$$, $$O(k^21.3995^k+|F|)$$ and $$O(1.1279^{|F|}|F|)$$ due to R. Niedermeier and P. Rossmanith [New Upper Bounds for MAXSAT’, International Colloquium on Automata, Languages and Programming (ICALP), Let. Notes Comput. Sci. (1999)] for these problems. Our last bound comes quite close to the $$O(1.07578^{|F|}|F|)$$ bound of E. A. Hirsch [Proceedings of the 9th annual ACM-SIAM symposium on Discrete algorithms. San Francisco, CA, USA, January 25-27 (1998). Philadelphia, PA: SIAM. 521-530 (1998; Zbl 0936.68113)] for the satisfiability problem (not MAXSAT).
For the entire collection see [Zbl 0933.00045].

##### MSC:
 68Q25 Analysis of algorithms and problem complexity
MAXSAT problem