Treffer: An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT

Title:
An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT
Authors:
ASANO, Takao
Source:
Foundations of computation theory (FCT 2003)Theoretical computer science. 354(3):339-353
Publisher Information:
Amsterdam: Elsevier, 2006.
Publication Year:
2006
Physical Description:
print, 11 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Analyse numérique. Calcul scientifique, Numerical analysis. Scientific computation, Analyse numérique, Numerical analysis, Approximation numérique, Numerical approximation, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Algorithme approximation, Approximation algorithm, Algoritmo aproximación, Informatique théorique, Computer theory, Informática teórica, Meilleure approximation, Best approximation, Mejor aproximación, Performance algorithme, Algorithm performance, Resultado algoritmo, Problème NP difficile, NP hard problem, Problema NP duro, MAX SAT, Relaxation LP, LP relaxation, LP-relaxation
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Information and System Engineering, Chuo University, Bunkyo-ku, Tokyo 112-8551, Japan
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=17635804
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.17635804
Database:
PASCAL Archive

Weitere Informationen

For MAX SAT, which is a well-known NP-hard problem, many approximation algorithms have been proposed. Two types of best approximation algorithms for MAX SAT were proposed by Asano and Williamson: one with best proven performance guarantee 0.7846 and the other with performance guarantee 0.8331 if the performance guarantee of the Zwick's algorithm for MAX SAT is as conjectured. Both algorithms are based on their sharpened analysis of Goemans and Williamson's LP-relaxation for MAX SAT. In this paper, we present an improved analysis which is simpler than the previous analysis. Furthermore, algorithms based on this analysis will play a role as a better building block in designing an improved approximation algorithm for MAX SAT. Actually we show an example that algorithms based on this analysis lead to approximation algorithms with performance guarantee 0.7877 and conjectured performance guarantee 0.8353 which are slightly better than the best known corresponding performance guarantees 0.7846 and 0.8331, respectively.