ON THE APPROXIMATION OF MAXIMUM SATISFIABILITY

Authors
YANNAKAKIS M
Citation
M. Yannakakis, ON THE APPROXIMATION OF MAXIMUM SATISFIABILITY, Journal of algorithms, 17(3), 1994, pp. 475-502
Citations number
39
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms → ACNP
ISSN journal
01966774
Volume
17
Issue
3
Year of publication
1994
Pages
475 - 502
Database
ISI
SICI code
0196-6774(1994)17:3<475:OTAOMS>2.0.ZU;2-1
Abstract
We present a 3/4 polynomial time approximation algorithm for the Maxim um Satisfiability problem: Given a set of clauses, find a truth assign ment that satisfies the maximum number of clauses. The algorithm appli es to the weighted case as well, and involves nontrivial application o f network flow techniques. (C) 1994 Academic Press, Inc.