Approximation Algorithms for the Maximum Satisfiability Problem
Approximation Algorithms for the Maximum Satisfiability Problem
复制标题
最大可满足性问题的近似算法
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
T. Hirata
中科院分区：
文献类型：
--
作者：
Takao Asano;Takao Ono;T. Hirata
最大可满足性问题（MAX SAT）是：给定一组具有权重的子句，求一个使满足子句的权重总和最大化的真值赋值。在本文中，我们提出了MAX SAT的近似算法，包括一个0.76544近似算法。先前的MAX SAT最佳逼近算法由Goemans-Williamson提出，性能保证为0.7584。我们的算法基于半定规划和Yannakakis和Goemans-Williamson的0.75近似算法。
The maximum satisfiability problem (MAX SAT) is: 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 present approximation algorithms for MAX SAT, including a 0.76544-approximation algorithm. The previous best approximation algorithm for MAX SAT was proposed by Goemans-Williamson and has a performance guarantee of 0.7584. Our algorithms are based on semidefinite programming and the 0.75-approximation algorithms of Yannakakis and Goemans-Williamson.