Improved exact algorithms for MAX-SAT

DOI10.1016/j.dam.2003.03.002zbMath1077.68116OpenAlexW2148185803MaRDI QIDQ1878397

Jian'er Chen, Iyad A. Kanj

Publication date: 19 August 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2003.03.002

zbMATH Keywords

Parameterized algorithmsExact algorithmsMaximum satisfiability

Mathematics Subject Classification ID

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

Related Items (16)

New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree ⋮ Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP ⋮ Improved MaxSAT Algorithms for Instances of Degree 3 ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ Approximating MAX SAT by moderately exponential and parameterized algorithms ⋮ Dealing with 4-variables by resolution: an improved MaxSAT algorithm ⋮ Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment ⋮ An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses ⋮ Almost 2-SAT is fixed-parameter tractable ⋮ Improved parameterized set splitting algorithms: A Probabilistic approach ⋮ Using the method of conditional expectations to supply an improved starting point for CCLS ⋮ Moderately exponential time and fixed parameter approximation algorithms ⋮ A refined branching algorithm for the maximum satisfiability problem

Uses Software

• DIMACS

Cites Work

• An improved fixed-parameter algorithm for vertex cover
• Algorithms for the maximum satisfiability problem
• On fixed-parameter tractability and approximability of NP optimization problems
• Which problems have strongly exponential complexity?
• A general method to speed up fixed-parameter-tractable algorithms
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover
• Vertex Cover: Further Observations and Further Improvements
• Integrity constraints in logic databases
• Algorithms for maximum independent sets
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• New Upper Bounds for Maximum Satisfiability
• A Computing Procedure for Quantification Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved exact algorithms for MAX-SAT