scientific article; zbMATH DE number 1263278

MaRDI QIDQ4234151zbMATH OpenFDO

Authors Michel X. Goemans, David P. Williamson

Publication date 16 March 1999

zbMATH Keywords

\({3\over 4}\)-approximation algorithmduality gaplinear programming relaxationmaximum satisfiability problemworst-case analysis

Mathematics Subject Classification ID

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

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

Cited in

(10)

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

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)