New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem (Q4317711)
From MaRDI portal
scientific article; zbMATH DE number 704660
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem |
scientific article; zbMATH DE number 704660 |
Statements
New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem (English)
0 references
20 December 1994
0 references
approximation algorithm
0 references
probabilistic method
0 references
performance guarantee
0 references
linear programming relaxations
0 references
maximum satisfiability problem
0 references
randomized rounding
0 references
worst-case analysis
0 references
