A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications

DOI10.1007/s00453-011-9550-1zbMath1252.68137arXiv1004.0526MaRDI QIDQ1759685

Xianqiang Yang

Publication date: 21 November 2012

Published in: Algorithmica, Parameterized and Exact Computation (Search for Journal in Brave)

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

zbMATH Keywords

lower bound; kernel; MaxSAT; fixed parameter tractable; 2-satisfiable

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)