𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Resolution for Max-SAT

✍ Scribed by María Luisa Bonet; Jordi Levy; Felip Manyà

Publisher
Elsevier Science
Year
2007
Tongue
English
Weight
179 KB
Volume
171
Category
Article
ISSN
0004-3702

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Exact Algorithms for MAX-SAT
Exact Algorithms for MAX-SAT
✍ Hantao Zhang; Haiou Shen; Felip Manyà 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 777 KB

The maximum satisfiability problem (MAX-SAT) is stated as follows: Given a boolean formula in CNF, find a truth assignment that satisfies the maximum possible number of its clauses. MAX-SAT is MAX-SNP-complete and received much attention recently. One of the challenges posed by Alber, Gramm and Nied

Improved Approximation Algorithms for MA
Improved Approximation Algorithms for MAX SAT
✍ Takao Asano; David P. Williamson 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 215 KB

MAX SAT (the maximum s~tisfiability problem) is stated as follows: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses. In this paper, we consider approxima~ tion algorithms for MAX SAT proposed by Goemans and Williamson and pze

On Approximation Algorithms for Hierarch
On Approximation Algorithms for Hierarchical MAX-SAT
✍ Sameet Agarwal; Anne Condon 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 232 KB

We prove upper and lower bounds on performance guarantees of approximation Ž . algorithms for the hierarchical MAX-SAT H-MAX-SAT problem. This problem is representative of a broad class of PSPACE-hard problems involving graphs, Boolean formulas, and other structures that are defined succinctly. Our