scientific article; zbMATH DE number 1263278

zbMATH Open0929.90071MaRDI QIDQ4234151FDOQ4234151

Authors: Michel X. Goemans, David P. Williamson 

Publication date: 16 March 1999

Title of this publication is not available (Why is that?)

Recommendations

• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• On the Approximation of Maximum Satisfiability
• Improved approximation algorithms for MAX SAT
• Simpler 3/4-approximation algorithms for MAX SAT

zbMATH Keywords

duality gapworst-case analysislinear programming relaxationmaximum satisfiability problem\({3\over 4}\)-approximation algorithm

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cited In (10)

• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Simpler 3/4-approximation algorithms for MAX SAT
• On dependent randomized rounding algorithms
• Rounding algorithms for covering problems
• Improved randomized approximation algorithms for lot-sizing problems
• On dependent randomized rounding algorithms
• Approximation algorithms for MAX-4-SAT and rounding procedures for semidefinite programs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Simultaneous approximation of constraint satisfaction problems
• Solving the maximum duo-preservation string mapping problem with linear programming

This page was built for publication:

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