zbMATH — the first resource for mathematics

Faster exact solutions for Max2Sat. (English) Zbl 0971.68598
Bongiovanni, Giancarlo (ed.) et al., Algorithms and complexity. 4th Italian conference, CIAC 2000, Rome, Italy, March 1-3, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1767, 174-186 (2000).
Summary: Given a booten 2CNF formula \(F\), the Max2Sat problem is that of finding the maximum number of clauses satisfiable simultaneously. In the corresponding decision version, we are given an additional parameter \(k\) and the question is whether we can simultaneously satisfy at least \(k\) clauses. This problem is NP-complete. We improve on known upper bounds on the worst case running time of Max2Sat, implying also new upper bounds for Maximum Cut. In particular, we give experimental results, indicating the practical relevance of our algorithms.
For the entire collection see [Zbl 0933.00042].

68U99 Computing methodologies and applications
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)