Dealing with 4-variables by resolution: an improved MaxSAT algorithm

DOI10.1016/J.TCS.2017.01.020MaRDI QIDQ515546zbMATH OpenOpenAlexFDO

Authors Chao Xu, Jianxin Wang, Jianer Chen

Publication date 16 March 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.02920

zbMATH Keywords

branch and boundparameterized algorithmmaximum satisfiabilityresolution principle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Abstract: We study techniques for solving the Maximum Satisfiability problem (MaxSAT). Our focus is on variables of degree 4. We identify cases for degree-4 variables and show how the resolution principle and the kernelization techniques can be nicely integrated to achieve more efficient algorithms for the MaxSAT problem. As a result, we present an algorithm of time $O^{\ast }(1.3248^k)$ for the MaxSAT problem, improving the previous best upper bound $O^{\ast }(1.358^k)$ by Ivan Bliznets and Alexander.

Recommendations

• Dealing with 4-variables by resolution: an improved \textsc{MaxSAT} algorithm
• Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms
• Improved \textsc{MaxSAT} algorithms for instances of degree 3
• Resolution for Max-SAT
• scientific article; zbMATH DE number 2086240

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1113992 (Why is no real title available?)
• scientific article; zbMATH DE number 1522934 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A new algorithm for parameterized MAX-SAT
• Algorithms – ESA 2005
• Approximation algorithms for NP-hard problems.
• Exact algorithms for dominating set
• Faster exact algorithms for hard problems: A parameterized point of view
• Improved approximation algorithms for MAX SAT
• Improved exact algorithms for MAX-SAT
• New Upper Bounds for Maximum Satisfiability
• On the Approximation of Maximum Satisfiability
• On the complexity of \(k\)-SAT
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• STACS 2005
• Vertex cover: Further observations and further improvements
• Which problems have strongly exponential complexity?

Cited in

(6)

• Further improvements for SAT in terms of formula length
• A refined branching algorithm for the maximum satisfiability problem
• Dealing with 4-variables by resolution: an improved \textsc{MaxSAT} algorithm
• scientific article; zbMATH DE number 7204399 (Why is no real title available?)
• Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms
• Improved \textsc{MaxSAT} algorithms for instances of degree 3

This page was built for publication: Dealing with 4-variables by resolution: an improved MaxSAT algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q515546)