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

DOI10.1016/j.tcs.2005.11.030zbMath1088.68181OpenAlexW2066372981MaRDI QIDQ2368971

Takao 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)

Related Items (1)

Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles

Uses Software

• Outward rotations

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
• Outward rotations
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

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