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

DOI10.1016/J.TCS.2017.01.020zbMATH Open1359.68121arXiv1503.02920OpenAlexW2585244063MaRDI QIDQ515546FDOQ515546

Authors: Chao Xu, Jianxin Wang, Jianer Chen 

Publication date: 16 March 2017

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

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.

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

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

zbMATH Keywords

branch and boundparameterized algorithmmaximum satisfiabilityresolution principle

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• A refined branching algorithm for the maximum satisfiability problem
• Dealing with 4-variables by resolution: an improved \textsc{MaxSAT} algorithm
• Title not available (Why is that?)
• Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms
• Improved \textsc{MaxSAT} algorithms for instances of degree 3
• Further improvements for SAT in terms of formula length

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)