Approximating MIN k-SAT
Approximating MIN k-SAT
复制标题
近似 MIN k-SAT
DOI：
10.1007/3-540-36136-7_41
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Uri Zwick
中科院分区：
文献类型：
--
作者：
A. Avidor;Uri Zwick
我们得到了大大改进的近似算法的MINK-SAT问题，叉= 2，3。更具体地说，我们得到了一个1.1037近似算法的MIN 2-SAT问题，改进了以前的1.5近似算法，和一个1.2136近似算法的MIN 3-SAT问题，改进了以前的1.75近似算法的问题。这些结果是通过调整技术，以前用于获得近似算法的MAXk-SAT问题。我们也得到了一些近似结果的硬度。
We obtain substantially improved approximation algorithms for the MINk-SAT problem, fork= 2,3. More specifically, we obtain a 1.1037-approximation algorithm for the MIN 2-SAT problem, improving a previous 1.5-approximation algorithm, and a 1.2136-approximation algorithm for the MIN 3-SAT problem, improving a previous 1.75-approximation algorithm for the problem. These results are obtained by adapting techniques that were previously used to obtain approximation algorithms for the MAXk-SAT problem. We also obtain some hardness of approximation results.