scientific article; zbMATH DE number 1263278

MaRDI QIDQ4234151zbMATH OpenFDO

Authors Michel X. Goemans, David P. Williamson

Publication date 16 March 1999

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)

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)

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