Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs
✍ Scribed by Eran Halperin; Uri Zwick
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 188 KB
- Volume
- 40
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
Karloff and Zwick obtained recently an optimal 7r8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7r8-approximation algorithm for MAX SAT, we consider the most natural generalization of MAX 3-SAT, namely MAX 4-SAT. We present a semidefinite programming relaxation of MAX 4-SAT and a new family of rounding procedures that try to cope well with clauses of various sizes. We study the potential, and the limitations, of the relaxation and of the proposed family of rounding procedures using a combination of theoretical and experimental means. We select two rounding procedures from the proposed family of rounding procedures. Using the first rounding procedure we seem to obtain an almost optimal 0.8721-approximation algorithm for MAX 4-SAT. Using the second rounding procedure we seem to obtain an optimal 7r8-approximation algorithm for satisfiable instances of MAX 4-SAT. On the other hand, we show that no rounding procedure from the family considered can be shown, using the current techniques, to yield an approximation algorithm for MAX 4-SAT whose performance guarantee for all instances of the problem is greater than 0.8724. We also show that the integrality ratio of the Ä 4 proposed relaxation, as a relaxation of MAX 1, 4 -SAT, is at most 0.8754.
The 0.8721-approximation for MAX 4-SAT that we seem to obtain substantially improves the performance guarantees of all previous algorithms suggested for the Ž . problem. It is extremely close to being optimal as a 7r8 q ⑀ -approximation algorithm for MAX 4-SAT, for any fixed ⑀ ) 0, would imply that P s NP. Our investigation also indicates, however, that additional ideas are required in order to obtain optimal 7r8-approximation algorithms for MAX 4-SAT and MAX SAT.
Although most of this paper deals specifically with the MAX 4-SAT problem, we believe that the new family of rounding procedures introduced and the methodology used in the design and in the analysis of the various rounding procedures considered have a much wider range of applicability.