On approximation algorithms for the minimum satisfiability problem
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 1306875 (Why is no real title available?)
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation algorithms for NP-hard problems.
- Approximation algorithms for combinatorial problems
- Depth-first search and the vertex cover problem
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- On the Approximation of Maximum Satisfiability
- Optimization, approximation, and complexity classes
- Planar Formulae and Their Uses
- Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
- Some simplified NP-complete graph problems
- The Minimum Satisfiability Problem
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
Cited in
(39)- ANALYSIS OF L-STRUCTURE OF POLYHEDRON IN THE PARTIAL MAX SAT PROBLEM
- Solving min ones 2-SAT as fast as vertex cover
- scientific article; zbMATH DE number 1688380 (Why is no real title available?)
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
- The Minimum Satisfiability Problem
- A primal-dual approximation algorithm for \textsc{minsat}
- Lower and Upper Bounds for Random Mimimum Satisfiability Problem
- A non-clausal tableau calculus for \textsc{MinSat}
- Fixed-parameter Approximability of Boolean MinCSPs
- Optimizing with minimum satisfiability
- A bounded approximation for the minimum cost 2-sat problem
- Single machine scheduling problems with uncertain parameters and the OWA criterion
- scientific article; zbMATH DE number 1979522 (Why is no real title available?)
- On reducing maximum independent set to minimum satisfiability
- Minimal sets on propositional formulae. Problems and reductions
- On the parallel parameterized complexity of MaxSAT variants
- Approximation bounds for the minimum \(k\)-storage problem
- The labeled perfect matching in bipartite graphs
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- On the Minimum Hitting Set of Bundles Problem
- On the greedy algorithm for satisfiability
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- Solving \textsc{minones-2-sat} as fast as \textsc{vertex cover}
- Approximation Algorithms for CSPs
- Revisiting maximum satisfiability and related problems in data streams
- Approximating MIN 2-SAT and MIN 3-SAT
- On the minimum hitting set of bundles problem
- (In)approximability of maximum minimal FVS
- Revisiting maximum satisfiability and related problems in data streams
- On the minimum satisfiability problem
- Complexity and approximations for submodular minimization problems on two variables per inequality constraints
- On minimizing the number of ADMs--tight bounds for an algorithm without preprocessing
- Mathematical Foundations of Computer Science 2004
- Set-weighted games and their application to the cover problem
- Differential approximation for optimal satisfiability and related problems
- Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
- Sparsification and subexponential approximation
- Approximation algorithms and hardness results for labeled connectivity problems
- On weighted vs unweighted versions of combinatorial optimization problems
This page was built for publication: On approximation algorithms for the minimum satisfiability problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1351157)
