A primal-dual approximation algorithm for \textsc{minsat}

DOI10.1016/j.dam.2021.07.016OpenAlexW3185428775WikidataQ113877226 ScholiaQ113877226MaRDI QIDQ2161258

Robert Benkoczi, Daya Ram Gaur, Ramesh Krishnamurti, Umair Arif

Publication date: 4 August 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2021.07.016

zbMATH Keywords

primal-dual schemaminimum satisfiability

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• On the hardness of approximating minimum vertex cover
• Efficient bounds for the stable set, vertex cover and set packing problems
• Approximation algorithms for combinatorial problems
• On approximation properties of the independent set problem for low degree graphs
• On dependent randomized rounding algorithms
• On approximation algorithms for the minimum satisfiability problem
• Which problems have strongly exponential complexity?
• Minimal sets on propositional formulae. Problems and reductions
• Sparsification and subexponential approximation
• Optimizing with minimum satisfiability
• Approximating MIN 2-SAT and MIN 3-SAT
• Complexity and approximations for submodular minimization problems on two variables per inequality constraints
• König-Egerváry graphs, 2-bicritical graphs and fractional matchings
• Approximating a generalization of MAX 2SAT and MIN 2SAT
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Berge's theorem for the maximum charge problem
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• On Reducing Maximum Independent Set to Minimum Satisfiability
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• The Minimum Satisfiability Problem
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Clause tableaux for maximum and minimum satisfiability
• A resolution calculus for MinSAT
• Answer Set Programming
• Paths, Trees, and Flowers
• Max flows in O(nm) time, or better
• The complexity of theorem-proving procedures

This page was built for publication: A primal-dual approximation algorithm for \textsc{minsat}