New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
From MaRDI portal
Publication:4317711
DOI10.1137/S0895480192243516zbMath0812.90129OpenAlexW2004660767MaRDI QIDQ4317711
David P. Williamson, Michel X. Goemans
Publication date: 20 December 1994
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480192243516
approximation algorithmprobabilistic methodworst-case analysisrandomized roundinglinear programming relaxationsmaximum satisfiability problemperformance guarantee
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorial optimization (90C27)
Related Items
An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT, Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}, On residual approximation in solution extension problems, Local Search to Approximate Max NAE-$$k$$-Sat Tightly, Complexity of approximating CSP with balance/hard constraints, Adding cardinality constraints to integer programs with applications to maximum satisfiability, On approximation algorithms for the minimum satisfiability problem, A nonmonotone GRASP, Improved approximation algorithms for the spanning star forest problem, A primal-dual approximation algorithm for \textsc{minsat}, Max Horn SAT and the minimum cut problem in directed hypergraphs, Revisiting maximum satisfiability and related problems in data streams, On Residual Approximation in Solution Extension Problems, Pricing commodities, Revisiting maximum satisfiability and related problems in data streams, Sublinear-space approximation algorithms for Max \(r\)-SAT, Combination algorithms for Steiner tree variants, A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem, Max NP-completeness made easy, Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\), Maximum renamable Horn sub-CNFs, Affine reductions for LPs and SDPs, Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, On the Lower Bounds of Random Max 3 and 4-SAT, Simple approximation algorithms for balanced MAX~2SAT, Approximating Max NAE-\(k\)-SAT by anonymous local search, Unnamed Item, On the lower bounds of random Max 3 and 4-SAT, Pseudo-Boolean optimization, An improved approximation algorithm for the partial Latin square extension problem., The approximability of non-Boolean satisfiability problems and restricted integer programming, An improved semidefinite programming relaxation for the satisfiability problem, Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?, Improved approximation algorithms for minimum power covering problems, Semidefinite Programming and Constraint Programming, An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses, An 0. 828-approximation algorithm for the uncapacitated facility location problem, Tight bound on Johnson's algorithm for maximum satisfiability, Unnamed Item, Approximation algorithms for fragmenting a graph against a stochastically-located threat, Improved approximation of maximum vertex cover, Packing items into several bins facilitates approximating the separable assignment problem, An approximation algorithm for the maximization version of the two level uncapacitated facility location problem, Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds, Maximum coverage with cluster constraints: an LP-based approximation technique, A refined branching algorithm for the maximum satisfiability problem
