Geodesic
New upper bounds for the problem of maximal satisfiability
Diskretnaya Matematika, Tome 21 (2009) no. 1, pp. 139-157

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we present relatively simple proofs of the following new upper bounds: $c^N$, where $c2$ 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. 
@article{DM_2009_21_1_a7,
     author = {A. S. Kulikov and K. Kutskov},
     title = {New upper bounds for the problem of maximal satisfiability},
     journal = {Diskretnaya Matematika},
     pages = {139--157},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2009_21_1_a7/}
}
TY  - JOUR
AU  - A. S. Kulikov
AU  - K. Kutskov
TI  - New upper bounds for the problem of maximal satisfiability
JO  - Diskretnaya Matematika
PY  - 2009
SP  - 139
EP  - 157
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2009_21_1_a7/
LA  - ru
ID  - DM_2009_21_1_a7
ER  - 
%0 Journal Article
%A A. S. Kulikov
%A K. Kutskov
%T New upper bounds for the problem of maximal satisfiability
%J Diskretnaya Matematika
%D 2009
%P 139-157
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2009_21_1_a7/
%G ru
%F DM_2009_21_1_a7
A. S. Kulikov; K. Kutskov. New upper bounds for the problem of maximal satisfiability. Diskretnaya Matematika, Tome 21 (2009) no. 1, pp. 139-157. http://geodesic.mathdoc.fr/item/DM_2009_21_1_a7/