Approximation Algorithms for MAX SAT

摘要

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 con- sidered. The aim of this survey is to show recent developments of approximation algorithms for MAX SAT.