Solving sparse instances of Max SAT via width reduction and greedy restriction
type: Item
instance of: scholarly article
title: Solving sparse instances of Max SAT via width reduction and greedy restriction
zbMATH Open document ID: 1347.68312
author: Takayuki Sakai
author: Kazuhisa Seto
author: Suguru Tamaki
published in: Theory of Computing Systems
publication date: 2016-01-28T00:00:00Z
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6536611
zbMATH Keywords: exponential time algorithm
zbMATH Keywords: polynomial space
zbMATH Keywords: weight
zbMATH Keywords: hard constraint
zbMATH Keywords: counting
describes a project that uses: MAX-2-SAT
MaRDI profile type: Publication
full work available at URL: s00224-014-9600-6
OpenAlex ID: W1983672233
cites work: Q4511230
cites work: A new upper bound for Max-2-SAT: A graph-theoretic approach
cites work: A New Algorithm for Parameterized MAX-SAT
cites work: A satisfiability algorithm and average-case hardness for formulas over the full binary basis
cites work: The Complexity of Satisfiability of Small Depth Circuits
cites work: Improved exact algorithms for MAX-SAT
cites work: Mining circuit lower bound proofs for meta-algorithms
cites work: MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time
cites work: A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
cites work: Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
cites work: Q2728900
cites work: Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
cites work: The Shrinkage Exponent of de Morgan Formulas is 2
cites work: Q4501522
cites work: Worst-case study of local search for MAX-\(k\)-SAT.
cites work: Computing Partitions with Applications to the Knapsack Problem
cites work: Q5743451
cites work: Mathematical Foundations of Computer Science 2005
cites work: A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms
cites work: Optimal 2-constraint satisfaction via sum-product algorithms
cites work: A new approach to proving upper bounds for MAX-2-SAT
cites work: Theory and Applications of Satisfiability Testing
cites work: New Bounds for MAX-SAT by Clause Learning
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: New Upper Bounds for Maximum Satisfiability
cites work: An algorithm for the satisfiability problem of formulas in conjunctive normal form
cites work: Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
cites work: Linear-programming design and analysis of fast algorithms for Max 2-CSP
cites work: A new algorithm for optimal 2-constraint satisfaction and its implications
cites work: Nonuniform ACC Circuit Lower Bounds
DOI: 10.1007/S00224-014-9600-6
Recommended article: Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction
Recommended article: Improved exact algorithms for mildly sparse instances of MAX SAT
Recommended article: Improved Exact Algorithms for Mildly Sparse Instances of Max SAT
Recommended article: Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
Recommended article: Bounds on Greedy Algorithms for MAX SAT
Recommended article: Q3604006
Recommended article: On Solving the Partial MAX-SAT Problem
Recommended article: Sparsification of SAT and CSP Problems via Tractable Extensions
Recommended article: Q5417644
Recommended article: An efficient solver for weighted Max-SAT
description: scientific article; zbMATH DE number 6536611