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

DOI10.1007/s00224-014-9600-6zbMath1347.68312OpenAlexW1983672233MaRDI QIDQ905695

Suguru Tamaki, Takayuki Sakai, Kazuhisa Seto

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

countingweightpolynomial spaceexponential time algorithmhard constraint

Mathematics Subject Classification ID

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

Related Items (2)

Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression

Uses Software

• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• Optimal 2-constraint satisfaction via sum-product algorithms
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Worst-case study of local search for MAX-\(k\)-SAT.
• Improved exact algorithms for MAX-SAT
• Mining circuit lower bound proofs for meta-algorithms
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Nonuniform ACC Circuit Lower Bounds
• New Bounds for MAX-SAT by Clause Learning
• A new approach to proving upper bounds for MAX-2-SAT
• The Complexity of Satisfiability of Small Depth Circuits
• Computing Partitions with Applications to the Knapsack Problem
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• The Shrinkage Exponent of de Morgan Formulas is 2
• New Upper Bounds for Maximum Satisfiability
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• A New Algorithm for Parameterized MAX-SAT
• A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms
• Mathematical Foundations of Computer Science 2005
• Theory and Applications of Satisfiability Testing
• MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

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