Improved exact algorithms for mildly sparse instances of MAX SAT

DOI10.1016/j.tcs.2017.07.011zbMath1379.68178OpenAlexW2739024676MaRDI QIDQ2405896

Junichi Teruyama, Suguru Tamaki, Kazuhisa Seto, Takayuki Sakai

Publication date: 28 September 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5574/

zbMATH Keywords

maximum satisfiabilitypolynomial spaceexponential spaceweighted

Mathematics Subject Classification ID

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

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
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• 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
• New exact algorithms for the 2-constraint satisfaction problem
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets
• A measure & conquer approach for the analysis of exact algorithms
• Powers of tensors and fast matrix multiplication
• Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
• New Bounds for MAX-SAT by Clause Learning
• A new approach to proving upper bounds for MAX-2-SAT
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• 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
• Improved Exact Algorithms for Mildly Sparse Instances of Max SAT
• 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: Improved exact algorithms for mildly sparse instances of MAX SAT