MAX SAT approximation beyond the limits of polynomial-time approximation

DOI10.1016/S0168-0072(01)00052-5MaRDI QIDQ5957907zbMATH OpenFDO

Authors E. Ya. Dantsin, Misha Gavrilovich, Edward A. Hirsch, B. Konev

Publication date 13 March 2002

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

Full work available at URL https://doi.org/10.1016/S0168-0072(01)00052-5

zbMATH Keywords

approximation algorithmsmaximum satisfiability problem

Mathematics Subject Classification ID

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

Recommendations

• On the Approximation of Maximum Satisfiability
• scientific article; zbMATH DE number 1552232
• scientific article; zbMATH DE number 1258327
• On Some Recent Approximation Algorithms for MAX SAT
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• Improved approximation algorithms for MAX SAT
• scientific article; zbMATH DE number 1445292
• scientific article; zbMATH DE number 1302170
• On the hardness of approximating max-satisfy

Cites work

• scientific article; zbMATH DE number 1670827 (Why is no real title available?)
• scientific article; zbMATH DE number 3747068 (Why is no real title available?)
• scientific article; zbMATH DE number 1522934 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• scientific article; zbMATH DE number 1405665 (Why is no real title available?)
• scientific article; zbMATH DE number 1445292 (Why is no real title available?)
• A machine program for theorem-proving
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• New worst-case upper bounds for SAT
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Solving satisfiability in less than \(2^ n\) steps
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cited in

(19)

• ANALYSIS OF L-STRUCTURE OF POLYHEDRON IN THE PARTIAL MAX SAT PROBLEM
• An exponential time 2-approximation algorithm for bandwidth
• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• Approximating a generalization of MAX 2SAT and MIN 2SAT
• Approximating maximum satisfiable subsystems of linear equations of bounded width
• On the hardness of approximating max-satisfy
• Exponential-time approximation of weighted set cover
• scientific article; zbMATH DE number 6297727 (Why is no real title available?)
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Super-polynomial approximation branching algorithms
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• MAX3SAT is exponentially hard to approximate if NP has positive dimension.
• A new algorithm for optimal 2-constraint satisfaction and its implications
• When polynomial approximation meets exact computation
• When polynomial approximation meets exact computation
• New Bounds for MAX-SAT by Clause Learning
• Moderately exponential time and fixed parameter approximation algorithms
• Further Reflections on a Theory for Basic Algorithms

This page was built for publication: MAX SAT approximation beyond the limits of polynomial-time approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5957907)