@article{oai:chuo-u.repo.nii.ac.jp:00001251,
 author = {ASANO, Takao},
 journal = {中央大学理工学研究所論文集},
 month = {Mar},
 note = {application/pdf, MAX SAT(maximum satisfiability problem) is stated as fllows: 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 approximation algorithms for MAX SAT proposed by Yannakakis and Goemans-Williamson and present an approximation algorithm which is an improvement of Yannakakis’ alforithm. Althoufh Yannakakis’ original algoritm has no better perfoemance guarantee than Goemans-Williamson, our improved algorithm has a better performance guarantee and leads to a 0.770-approximation algorithm., 【査読有】},
 pages = {57--77},
 title = {An Improvement of Yannakaki's Algorithm for MAX SAT},
 volume = {9},
 year = {2004}
}