An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses
type: Item
instance of: scholarly article
title: An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses
zbMATH Open document ID: 1481.90280
author: Chao Xu
author: Wen-Jun Li
author: Jianxin Wang
author: Yongjie Yang
published in: Journal of Combinatorial Optimization
publication date: 2021-11-25T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 7433400
zbMATH Keywords: CNF formula
zbMATH Keywords: 3-SAT
zbMATH Keywords: branching algorithm
zbMATH Keywords: complexity
zbMATH Keywords: parameterized complexity
describes a project that uses: UnitWalk
describes a project that uses: CCEHC
MaRDI profile type: Publication
full work available at URL: s10878-019-00421-1
OpenAlex ID: W2946508068
cites work: Exact Max-SAT solvers for over-constrained problems
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Q4511230
cites work: A New Algorithm for Parameterized MAX-SAT
cites work: A new upper bound for \(( n , 3)\)-MAX-SAT
cites work: Resolution for Max-SAT
cites work: Improved exact algorithms for MAX-SAT
cites work: Improved upper bounds for vertex cover
cites work: The complexity of theorem-proving procedures
cites work: Exact exponential algorithms.
cites work: Q4198056
cites work: New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: New worst-case upper bounds for SAT
cites work: UnitWalk: A new SAT solver that uses local search guided by unit clause elimination
cites work: Q3002852
cites work: The configurable SAT solver challenge (CSSC)
cites work: On the complexity of \(k\)-SAT
cites work: Theory and Applications of Satisfiability Testing
cites work: An improved branching algorithm for \((n,3)\)-MaxSAT based on refined observations
cites work: CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability
cites work: New Upper Bounds for Maximum Satisfiability
cites work: Q5417690
cites work: Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
cites work: A simplified NP-complete MAXSAT problem
cites work: MaxSAT-Based Cutting Planes for Learning Graphical Models
cites work: Generating hard satisfiability problems
cites work: Improving exact algorithms for MAX-2-SAT
cites work: An exact algorithm for maximum independent set in degree-5 graphs
DOI: 10.1007/S10878-019-00421-1
description: scientific article; zbMATH DE number 7433400