Approximation algorithms for MAX SAT: Yannakakis vs Goemans-Williamson

被引：17

作者：

Asano, T

机构：

来源：

PROCEEDINGS OF THE FIFTH ISRAELI SYMPOSIUM ON THEORY OF COMPUTING AND SYSTEMS | 1997年

关键词：

D O I：

10.1109/ISTCS.1997.595154

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

MAX SAT (the maximum satisfiability problem) is stated as follows: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses. fn this paper, we consider approximation algorithms for MAX SA proposed by Yannakakis and Goemans-Williamson and present an approximation algorithm which is an improvement of Yannakakis' algorithm. Although Yannakakis' original algorithm has no better performance guarantee than Goemans-Williamson, our improved algorithm has a better performance guarantee and leads to a 0.770-approximation algorithm.

引用

页码：24 / 37

页数：14