An Improvement of Yannakaki's Algorithm for MAX SAT

公開日:2012.10.01

発行日
2004年03月31日
概要
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.【査読有】
文献等

掲載誌名・書名:

中央大学理工学研究所論文集, 第9号/2003, pp.57-77

公開者・出版社:

中央大学理工学研究所

書誌コード類:

ISSN: 1343-0068

種類
論文
言語
英語
権利情報
この資料の著作権は、資料の著作者または学校法人中央大学に帰属します。著作権法が定める私的利用・引用を超える使用を希望される場合には、掲載誌発行部局へお問い合わせください。

このページのTOPへ