A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
From MaRDI portal
Publication:1759685
DOI10.1007/s00453-011-9550-1zbMath1252.68137arXiv1004.0526OpenAlexW2118469858MaRDI QIDQ1759685
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
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 11 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
