Approximating MIN 2-SAT and MIN 3-SAT

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,...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2005-05, Vol.38 (3), p.329-345
Main Authors: Avidor, Adi, Zwick, Uri
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Boolean
Computer science
Linear programming
Random variables
Semidefinite programming
Studies
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. [PUBLICATION ABSTRACT]
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-005-1140-7