×

zbMATH — the first resource for mathematics

New upper bounds for the problem of maximal satisfiability. (English. Russian original) Zbl 1234.68154
Discrete Math. Appl. 19, No. 2, 155-172 (2009); translation from Diskretn. Mat. 21, No. 1, 139-157 (2009).
Summary: In this paper we present relatively simple proofs of the following new upper bounds for MAX-SAT and MAX-2-SAT:
– \(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.

MSC:
68Q25 Analysis of algorithms and problem complexity
Software:
SATO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chen J., Lecture Notes Computer Sci. 2286 pp 341– (2002) · doi:10.1007/3-540-45995-2_32
[2] Dantsin E., Lecture Notes Computer Sci. 4121 pp 266– (2006) · Zbl 1187.68258 · doi:10.1007/11814948_26
[3] Fedin S. S., J. Math. Sci. 134 (5) pp 2383– (2006) · doi:10.1007/s10958-006-0114-x
[4] Gramm J., Discrete Appl. Math. 130 (2) pp 139– (2003) · Zbl 1051.68078 · doi:10.1016/S0166-218X(02)00402-X
[5] Kneis J., Lecture Notes Computer Sci. 3787 pp 385– (2005) · doi:10.1007/11604686_34
[6] Kulikov A. S., Lecture Notes Computer Sci. 3569 pp 430– (2005) · doi:10.1007/11499107_35
[7] Kulikov A. S., Lecture Notes Computer Sci. 4549 pp 194– (2007) · Zbl 1188.68272 · doi:10.1007/978-3-540-74510-5_21
[8] Kullmann O., Theoret. Computer Sci. 223 pp 1– (1997) · Zbl 0930.68066 · doi:10.1016/S0304-3975(98)00017-6
[9] Marques-Silva J. P., IEEE Trans. Comput. 48 (5) pp 506– (1999) · Zbl 01935259 · doi:10.1109/12.769433
[10] R., Lecture Notes Computer Sci. 1644 pp 575– (1999) · doi:10.1007/3-540-48523-6_54
[11] Poljak S., Ser. Discrete Math. Theor. Comput. Sci. 20 pp 181– (1995)
[12] Robson J. M., J. Algorithms 7 (3) pp 425– (1986) · Zbl 0637.68080 · doi:10.1016/0196-6774(86)90032-5
[13] Scott A. D., Discrete Optimization 4 pp 260– (2007) · Zbl 1153.90505 · doi:10.1016/j.disopt.2007.08.001
[14] Scott A. D., Lecture Notes Computer Sci. 2764 pp 382– (2003) · doi:10.1007/978-3-540-45198-3_32
[15] Williams R., Lecture Notes Computer Sci. 2919 pp 330– (2003) · doi:10.1007/978-3-540-24605-3_25
[16] Williams R., Theoret. Computer Sci. 348 pp 357– (2005) · Zbl 1081.68095 · doi:10.1016/j.tcs.2005.09.023
[17] Zhang H., Lecture Notes Computer Sci. 1249 pp 272– (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.