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].

68Q25 Analysis of algorithms and problem complexity
MAXSAT problem