Breaking Cycle Structure to Improve Lower Bound for Max-SAT

DOI10.1007/978-3-319-39817-4_12zbMath1475.68350OpenAlexW2480334143MaRDI QIDQ4632177

Chu-Min Li, Kun He, Yi Fan, Yanli Liu

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-39817-4_12

zbMATH Keywords

branch and boundNP-completenesslower boundMax-SAT

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) (68V15)

Uses Software

• UBCSAT
• MaxHS
• CCLS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• SAT-based MaxSAT algorithms
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Resolution-based lower bounds in MaxSAT
• Resolution for Max-SAT
• CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
• Exploiting Unit Propagation to Compute Lower Bounds in Branch and Bound Max-SAT Solvers
• Exploiting Cycle Structures in Max-SAT
• New Upper Bounds for Maximum Satisfiability
• A machine program for theorem-proving
• The complexity of theorem-proving procedures
• Theory and Applications of Satisfiability Testing

This page was built for publication: Breaking Cycle Structure to Improve Lower Bound for Max-SAT