An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses
From MaRDI portal
Publication:2051907
DOI10.1007/s10878-019-00421-1zbMath1481.90280OpenAlexW2946508068MaRDI QIDQ2051907
Wenjun Li, Yongjie Yang, Jianxin Wang, Chao Xu
Publication date: 25 November 2021
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-019-00421-1
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simplified NP-complete MAXSAT problem
- The configurable SAT solver challenge (CSSC)
- CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability
- Exact exponential algorithms.
- Improved upper bounds for vertex cover
- Improving exact algorithms for MAX-2-SAT
- An exact algorithm for maximum independent set in degree-5 graphs
- Resolution for Max-SAT
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- New worst-case upper bounds for SAT
- An improved branching algorithm for \((n,3)\)-MaxSAT based on refined observations
- UnitWalk: A new SAT solver that uses local search guided by unit clause elimination
- Improved exact algorithms for MAX-SAT
- A new upper bound for \(( n , 3)\)-MAX-SAT
- Exact Max-SAT solvers for over-constrained problems
- Generating hard satisfiability problems
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- New Upper Bounds for Maximum Satisfiability
- A New Algorithm for Parameterized MAX-SAT
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- The complexity of theorem-proving procedures
- Theory and Applications of Satisfiability Testing
- MaxSAT-Based Cutting Planes for Learning Graphical Models
- On the complexity of \(k\)-SAT
