Resolution for Max-SAT
From MaRDI portal
Publication:1028942
DOI10.1016/J.ARTINT.2007.03.001zbMATH Open1168.68541OpenAlexW2154352023WikidataQ60512184 ScholiaQ60512184MaRDI QIDQ1028942
Maria Luisa Bonet, Jordi Levy, Felip Manya
Publication date: 9 July 2009
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.artint.2007.03.001
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
- Exploiting Unit Propagation to Compute Lower Bounds in Branch and Bound Max-SAT Solvers
- Hard examples for resolution
- A Computing Procedure for Quantification Theory
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for resolution and cutting plane proofs and monotone computations
- A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
- The approximability of constraint satisfaction problems
- Short proofs are narrow—resolution made simple
- The intractability of resolution
- Resolution lower bounds for the weak pigeonhole principle
- New Upper Bounds for Maximum Satisfiability
- Exact Algorithms for MAX-SAT
- On the automatizability of resolution and related propositional proof systems
- Mutilated chessboard problem is exponentially hard for resolution
- The efficiency of resolution and Davis-Putnam procedures
- Local Consistency in Weighted CSPs and Inference in Max-SAT
- A Complete Calculus for Max-SAT
- Bucket elimination for multiobjective optimization problems
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- Principles and Practice of Constraint Programming – CP 2004
Cited In (30)
- Resolution-based lower bounds in MaxSAT
- A framework for reasoning under uncertainty based on non-deterministic distance semantics
- Simplified forms of computerized reasoning with distance semantics
- A proof builder for Max-SAT
- Improved MaxSAT Algorithms for Instances of Degree 3
- Exploiting Cycle Structures in Max-SAT
- Breaking Cycle Structure to Improve Lower Bound for Max-SAT
- Propositional proof systems based on maximum satisfiability
- MaxSAT Resolution and Subcube Sums
- A Max-SAT Inference-Based Pre-processing for Max-Clique
- ahmaxsat: Description and Evaluation of a Branch and Bound Max-SAT Solver
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Understanding the power of Max-SAT resolution through up-resilience
- Iterative and core-guided maxsat solving: a survey and assessment
- An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses
- Boosting branch-and-bound MaxSAT solvers with clause learning
- Certified Core-Guided MaxSAT Solving
- Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
- Theory and Applications of Satisfiability Testing
- Applications and Computational Advances for Solving the QUBO Model
- Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms
- Incomplete inference for graph problems
- MaxSAT resolution for regular propositional logic
- Cable tree wiring -- benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints
- Proofs and Certificates for Max-SAT
- Maximal minimal resolutions
- QMaxSATpb: a certified MaxSAT solver
- Polynomial calculus for optimization
- Algorithms for Weighted Boolean Optimization
- WPM3: an (in)complete algorithm for weighted partial MaxSAT
This page was built for publication: Resolution for Max-SAT
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1028942)
