An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses

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

zbMATH Keywords

complexityparameterized complexity3-SATbranching algorithmCNF formula

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Uses Software

• UnitWalk
• CCEHC

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