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.0526OpenAlexW2118469858MaRDI 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 boundkernelMaxSATfixed parameter tractable2-satisfiable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Related Items (7)

Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Parameterized complexity of MaxSat above average ⋮ A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ Unnamed Item ⋮ Fixed-parameter tractability of satisfying beyond the number of variables ⋮ A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application ⋮ Parameterizations of test cover with bounded test sizes

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity of partial satisfaction. II.
• Implications of forbidden structures for extremal algorithmic problems
• Solving satisfiability in less than \(2^ n\) steps
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• E ₁₁ and M theory
• A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application
• Kernels: Annotated, Proper and Induced
• Partial Satisfaction of k-Satisfiable Formulas
• Lower Bounds for Kernelizations and Other Preprocessing Procedures
• Complexity of Partial Satisfaction
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• On the Approximation of Maximum Satisfiability
• On Local Versus Global Satisfiability

This page was built for publication: A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications