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

DOI10.1016/J.TCS.2005.11.030MaRDI QIDQ2368971zbMATH OpenOpenAlexFDO

Authors T. Asano

Publication date 28 April 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.11.030

zbMATH Keywords

Approximation algorithmLP-relaxationMAX SAT

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT.
• Improved approximation algorithms for MAX SAT
• scientific article; zbMATH DE number 1445292
• Approximation and Online Algorithms
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem

Cites work

• Approximation algorithms for combinatorial problems
• Approximation algorithms for MAX-4-SAT and rounding procedures for semidefinite programs
• Improved approximation algorithms for MAX SAT
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems

Cited in

(4)

• Go-MOCE: greedy order method of conditional expectations for Max Sat
• ANALYSIS OF L-STRUCTURE OF POLYHEDRON IN THE PARTIAL MAX SAT PROBLEM
• An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT.
• Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles

Describes a project that uses

Uses Software

• Outward rotations

This page was built for publication: An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT

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