Title: New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
Abstract: Yannakakis recently presented the first $\frac{3}{4}$-approximation algorithm for the Maximum Satisfiability Problem (MAX SAT). His algorithm makes nontrivial use of solutions to maximum flow problems. New, simple $\frac{3}{4}$-approximation algorithms that apply the probabilistic method/randomized rounding to the solution to a linear programming relaxation of MAX SAT are presented. It is shown that although standard randomized rounding does not give a good approximate result, the best solution of the two given by randomized rounding and a well-known algorithm of Johnson is always within $\frac{3}{4}$ of the optimal solution. It is further shown that an unusual twist on randomized rounding also yields 4-approximation algorithms. As a by-product of the analysis, a tight worst-case analysis of the relative duality gap of the linear programming relaxation is obtained.
Publication Year: 1994
Publication Date: 1994-11-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 230
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot