Approximate Algorithms and Heuristics for MAX-SAT

Roberto Battiti () and Marco Protasi ()
Additional contact information
Roberto Battiti: Università di Trento, Dipartimento di Matematica
Marco Protasi: Università di Roma “Tor Vergata”, Dipartimento di Matematica

A chapter in Handbook of Combinatorial Optimization, 1998, pp 77-148 from Springer

Abstract: Abstract In the Maximum Satisfiability (MAX-SAT) problem one is given a Boolean formula in conjunctive normal form, i.e., as a conjunction of clauses, each clause being a disjunction. The task is to find an assignment of truth values to the variables that satisfies the maximum number of clauses.

Keywords: Local Search; Integer Linear Programming; Performance Ratio; Approximate Algorithm; Truth Assignment (search for similar items in EconPapers)
Date: 1998
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-0303-9_2

Ordering information: This item can be ordered from
http://www.springer.com/9781461303039

DOI: 10.1007/978-1-4613-0303-9_2

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().