Approximation algorithms for MAX-4-SAT and rounding procedures for semidefinite programs

DOI10.1006/JAGM.2001.1162MaRDI QIDQ2746433zbMATH OpenOpenAlexFDO

Authors Eran Halperin, Uri Zwick

Publication date 1 December 2002

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.2001.1162

Mathematics Subject Classification ID

Approximation algorithms (68W25) Semidefinite programming (90C22)

Recommendations

• scientific article; zbMATH DE number 1342131
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• scientific article; zbMATH DE number 1263278
• scientific article; zbMATH DE number 2086914

Cited in

(9)

• An improved semidefinite programming relaxation for the satisfiability problem
• An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT
• Semidefinite programming and constraint programming
• scientific article; zbMATH DE number 1342131 (Why is no real title available?)
• scientific article; zbMATH DE number 2086914 (Why is no real title available?)
• scientific article; zbMATH DE number 2119703 (Why is no real title available?)
• scientific article; zbMATH DE number 956857 (Why is no real title available?)
• On the mysteries of MAX NAE-SAT
• Separating \textsc{max} 2-and, \textsc{max di-cut}, and \textsc{max cut}

This page was built for publication: Approximation algorithms for MAX-4-SAT and rounding procedures for semidefinite programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2746433)