TY - JOUR

T1 - New upper bounds for the problem of maximal satisfiability

AU - Kulikov, A. S.

AU - Kutskov, K.

PY - 2009/5/1

Y1 - 2009/5/1

N2 - In this paper we present relatively simple proofs of the following new upper bounds: cN, 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.

AB - In this paper we present relatively simple proofs of the following new upper bounds: cN, 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.

UR - http://www.scopus.com/inward/record.url?scp=67650092015&partnerID=8YFLogxK

U2 - 10.1515/DMA.2009.009

DO - 10.1515/DMA.2009.009

M3 - Article

AN - SCOPUS:67650092015

VL - 19

SP - 155

EP - 172

JO - Discrete Mathematics and Applications

JF - Discrete Mathematics and Applications

SN - 0924-9265

IS - 2

ER -