✦ LIBER ✦

New Upper Bounds for Maximum Satisfiability

✍ Scribed by Rolf Niedermeier; Peter Rossmanith

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 168 KB
Volume: 36
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1075

No coin nor oath required. For personal study only.

✦ Synopsis

The unweighted Maximum Satisfiability problem MAXSAT is: Given a Boolean formula in conjunctive normal form, find a truth assignment that satisfies the largest number of clauses. This paper describes exact algorithms that provide new Ž< < upper bounds for MAXSAT. We prove that MAXSAT can be solved in time O F и K . < < 1.3803 , where F is the length of a formula F in conjunctive normal form and K Ž< < k . is the number of clauses in F. We also prove the time bounds O F и 1.3995 ,

where k is the maximum number of satisfiable clauses, and O 1.1279 , for the Ž K . same problem. For MAX2SAT this implies a bound of O 1.2722 . ᮊ 2000 Academic Press

📜 SIMILAR VOLUMES

Tight Bound on Johnson's Algorithm for M

Tight Bound on Johnson's Algorithm for Maximum Satisfiability

✍ Jianer Chen; Donald K. Friesen; Hao Zheng 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 223 KB

We present new techniques that give a more thorough analysis on Johnson's classical algorithm for the Maximum Satisfiability problem. In contrast to the common belief for two decades that Johnson's Algorithm has performance ratio 1Â2, we show that the performance ratio is 2Â3 and that this bound is

New Upper Bounds for Ramsey Numbers

✍ Y.R Huang; K.M Zhang 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 79 KB

The Ramsey number R(G 1 , G 2 ) is the smallest integer p such that for any graph Some new upper bound formulas are obtained for R(G 1 , G 2 ) and R(m, n), and we derive some new upper bounds for Ramsey numbers here.

New Upper Bounds for Finite Bh Sequences

✍ Javier Cilleruelo 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 258 KB

Let F h (N) be the maximum number of elements that can be selected from the set [1, ..., N] such that all the sums a 1 + } } } +a h , a 1 } } } a h are different. We introduce new combinatorial and analytic ideas to prove new upper bounds for F h (N). In particular we prove Besides, our techniques

A General Upper Bound for the Satisfiabi

A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae

✍ O Dubois; Y Boufkhad 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 280 KB

Experiments on solving r-SAT random formulae have provided evidence of a satisfiability threshold phenomenon with respect to the ratio of the number of clauses to the number of variables of formulae. Presently, only the threshold of 2-SAT formulae has been proved to exist and has been computed to be

New Upper and Lower Bounds for Ramsey Nu

New Upper and Lower Bounds for Ramsey Numbers

✍ Huang Yi Ru; Yang Jian Sheng 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 76 KB

Upper bounds for harmonious colorings

✍ Colin McDiarmid; Luo Xinhua 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 301 KB

## Abstract A harmonious coloring of a simple graph __G__ is a coloring of the vertices such that adjacent vertices receive distinct colors and each pair of colors appears together on at most one edge. The harmonious chromatic number __h__(__G__) is the least number of colors in such a coloring. We