On approximation algorithms for the minimum satisfiability problem
From MaRDI portal
Publication:1351157
DOI10.1016/0020-0190(96)00031-2zbMath0875.68544OpenAlexW2030702117MaRDI QIDQ1351157
Publication date: 27 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(96)00031-2
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (21)
Single machine scheduling problems with uncertain parameters and the OWA criterion ⋮ Lower and Upper Bounds for Random Mimimum Satisfiability Problem ⋮ From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ A primal-dual approximation algorithm for \textsc{minsat} ⋮ Minimal sets on propositional formulae. Problems and reductions ⋮ Revisiting maximum satisfiability and related problems in data streams ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ On the Minimum Hitting Set of Bundles Problem ⋮ Revisiting maximum satisfiability and related problems in data streams ⋮ Sparsification and subexponential approximation ⋮ A non-clausal tableau calculus for \textsc{MinSat} ⋮ ANALYSIS OF L-STRUCTURE OF POLYHEDRON IN THE PARTIAL MAX SAT PROBLEM ⋮ Optimizing with minimum satisfiability ⋮ Complexity and approximations for submodular minimization problems on two variables per inequality constraints ⋮ On the minimum hitting set of bundles problem ⋮ The labeled perfect matching in bipartite graphs ⋮ Set-weighted games and their application to the cover problem ⋮ On weighted vs unweighted versions of combinatorial optimization problems ⋮ Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems. ⋮ On subexponential and FPT-time inapproximability ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
Cites Work
- Depth-first search and the vertex cover problem
- Optimization, approximation, and complexity classes
- Approximation algorithms for combinatorial problems
- Some simplified NP-complete graph problems
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- .879-approximation algorithms for MAX CUT and MAX 2SAT
- Planar Formulae and Their Uses
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- The Minimum Satisfiability Problem
- Approximation algorithms for NP-complete problems on planar graphs
- On the Approximation of Maximum Satisfiability
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On approximation algorithms for the minimum satisfiability problem
