Approximation Algorithms for MAX SAT

Tomio HIRATA  Takao ONO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.3   pp.488-495
Publication Date: 2000/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Approximate Algorithms for Combinatorial Problems
Keyword: 
MAX SAT,  approximation algorithms,  semidefinite programming,  

Full Text: PDF(353.4KB)>>
Buy this Article



Summary: 
Maximum Satisfiability Problem (MAX SAT) is one of the most natural optimization problems. Since it is known to be NP-hard, approximation algorithms have been considered. The aim of this survey is to show recent developments of approximation algorithms for MAX SAT.