Solving sparse instances of Max SAT via width reduction and greedy restriction
From MaRDI portal
Publication:905695
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
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
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
