Solving sparse instances of Max SAT via width reduction and greedy restriction

DOI10.1007/S00224-014-9600-6MaRDI QIDQ905695zbMATH OpenOpenAlexFDO

Authors Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki

Publication date 28 January 2016

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-014-9600-6

zbMATH Keywords

countingexponential time algorithmhard constraintpolynomial spaceweight

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Improved exact algorithms for mildly sparse instances of MAX SAT
• Improved exact algorithms for mildly sparse instances of MAX SAT
• Improved algorithms for sparse MAX-SAT and MAX-k-CSP
• Bounds on greedy algorithms for MAX SAT
• Solving weighted Max-SAT problems in a reduced search space: a performance analysis
• On Solving the Partial MAX-SAT Problem
• Sparsification of SAT and CSP Problems via Tractable Extensions
• scientific article; zbMATH DE number 6297727
• An efficient solver for weighted Max-SAT

Cites work

• A bound on the pathwidth of sparse graphs with applications to exact algorithms
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A new algorithm for parameterized MAX-SAT
• A new approach to proving upper bounds for MAX-2-SAT
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• Computing Partitions with Applications to the Knapsack Problem
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• scientific article; zbMATH DE number 1629855 (Why is no real title available?)
• scientific article; zbMATH DE number 1500507 (Why is no real title available?)
• scientific article; zbMATH DE number 1522934 (Why is no real title available?)
• Improved exact algorithms for MAX-SAT
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• Mathematical Foundations of Computer Science 2005
• MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time
• Mining circuit lower bound proofs for meta-algorithms
• New Bounds for MAX-SAT by Clause Learning
• New Upper Bounds for Maximum Satisfiability
• Nonuniform ACC circuit lower bounds
• Optimal 2-constraint satisfaction via sum-product algorithms
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• The complexity of satisfiability of small depth circuits
• The Shrinkage Exponent of de Morgan Formulas is 2
• Theory and Applications of Satisfiability Testing
• Worst-case study of local search for MAX-\(k\)-SAT.
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cited in

(5)

• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• Improved exact algorithms for mildly sparse instances of MAX SAT
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Improved algorithms for sparse MAX-SAT and MAX-k-CSP
• Improved exact algorithms for mildly sparse instances of MAX SAT

Describes a project that uses

Uses Software

• MAX-2-SAT

This page was built for publication: Solving sparse instances of Max SAT via width reduction and greedy restriction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q905695)