Improved approximation algorithms for MAX SAT
Improved approximation algorithms for MAX SAT
复制标题
DOI：
10.1006/jagm.2001.1202
复制
发表时间：
2000-02
期刊：
影响因子：
--
通讯作者：
Takao Asano;David P. Williamson
中科院分区：
文献类型：
--
作者：
Takao Asano;David P. Williamson
Max SAT（最大满意度问题）如下：给定一组具有权重的子句，找到一个真实分配，以最大化满意条款的权重。在本文中，我们考虑了Goemans和Williamson提出的Max SAT的近似算法，并对其性能保证进行了加强的分析。我们还表明，由于Feige和Goemans，Karloff和Zwick以及Zwick，这些算法以及最大2SAT，MAX 3SAT和MAX SAT的最新近似算法以及Max SAT的最新算法，以及Max SAT的改进近似算法。通过使用MAX 2SAT和3SAT算法，我们获得了0.7846的性能保证，并且使用Zwick的算法，我们获得了0.8331的性能保证，该保证根据Zwick的猜想提高了0.7977的性能保证。 Max SAT的最佳先前结果在不假设Zwick的猜想的情况下是Asano的0.770- approximation算法。我们的最佳算法需要一个新的34个附属算法的家庭，这些算法概括了Goemans和Williamson的先前算法。
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. In this paper, we consider approximation algorithms for MAX SAT proposed by Goemans and Williamson and present a sharpened analysis of their performance guarantees. We also show that these algorithms, combined with recent approximation algorithms for MAX 2SAT, MAX 3SAT, and MAX SAT due to Feige and Goemans, Karloff and Zwick, and Zwick, respectively, lead to an improved approximation algorithm for MAX SAT. By using the MAX 2SAT and 3SAT algorithms, we obtain a performance guarantee of 0.7846, and by using Zwick's algorithm, we obtain a performance guarantee of 0.8331, which improves upon the performance guarantee of 0.7977 based on Zwick's conjecture. The best previous result for MAX SAT without assuming Zwick's conjecture is a 0.770-approximation algorithm of Asano. Our best algorithm requires a new family of 34-approximation algorithms that generalize a previous algorithm of Goemans and Williamson.