New upper bounds for the problem of maximal satisfiability
Alexander S. Kulikov, K. Kutskov · Discrete Mathematics and Applications · 2009
In this paper we present relatively simple proofs of the following new upper bounds: c N , where c < 2 is a constant and N is the number of variables, for MAX-SAT for formulas with constant clause density; 2 K /6 , where K is the number of clauses, for MAX-2-SAT; 2 N /6.7 for ( n , 3)-MAX-2-SAT. All bounds are proved by the splitting method. The main two techniques are combined complexity measures and clause learning.