未找到相关数据
Approximating MIN 2-SAT and MIN 3-SAT
被引：0
作者：
Adi Avidor
Uri Zwick
机构：
[1] School of Computer Science,
[2] Tel-Aviv University,undefined
[3] Tel-Aviv 69978,undefined
来源：
Theory of Computing Systems
|
2005年
/
38卷
关键词：
Computational Mathematic;
Approximation Algorithm;
Approximation Result;
Improve Approximation Algorithm;
Obtain Approximation Algorithm;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We obtain substantially improved approximation algorithms for the MIN k-SAT problem, for k = 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 MAX k-SAT problem. We also obtain some hardness of approximation
results.
引用
收藏
页码：329 / 345
页数：16
相关论文
未找到相关数据