Recently there was a significant progress in proving (exponential-time) worst-case upper bounds for the propositional satisfiability problem (SAT) and related problems. In particular, for MAX-2-SAT Niedermeier and Rossmanith recently presented an algorithm with worst-case upper bound O(K-2 K/2.88... ), and the bound O(K-2 K/3.44... ) is implicit from the paper by Bansal and Raman (K is the number of clauses). In this paper we improve this bound to p(K)2 K2/4 , where K 2  is the number of 2-clauses, and p is a polynomial. In addition, our algorithm and the proof are much simpler than the previous ones. The key ideas are to use the symmetric flow algorithm of Yannakakis and to count only 2-clauses (and not 1-clauses).
['Edward A. Hirsch']
A new algorithm for MAX-2-SAT