𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Improving exact algorithms for MAX-2-SAT

✍ Scribed by Haiou Shen; Hantao Zhang

Publisher
Springer Netherlands
Year
2005
Tongue
English
Weight
270 KB
Volume
44
Category
Article
ISSN
1012-2443

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