MAX SAT approximation beyond the limits of polynomial-time approximation

DOI10.1016/S0168-0072(01)00052-5zbMath0990.03006MaRDI QIDQ5957907

Edward A. Hirsch, Evgeny Dantsin, Boris Konev, Michael Gavrilovich

Publication date: 13 March 2002

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsmaximum satisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Mechanization of proofs and logical operations (03B35) Classical propositional logic (03B05) Approximation algorithms (68W25)

Related Items

An exponential time 2-approximation algorithm for bandwidth ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Super-polynomial approximation branching algorithms ⋮ Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. ⋮ When polynomial approximation meets exact computation ⋮ Approximating MAX SAT by moderately exponential and parameterized algorithms ⋮ When polynomial approximation meets exact computation ⋮ Exponential-time approximation of weighted set cover ⋮ MAX3SAT is exponentially hard to approximate if NP has positive dimension. ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ Moderately exponential time and fixed parameter approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving satisfiability in less than \(2^ n\) steps
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• New worst-case upper bounds for SAT
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A machine program for theorem-proving