Improved algorithms for sparse MAX-SAT and MAX-k-CSP

DOI10.1007/978-3-319-24318-4_4MaRDI QIDQ3453207zbMATH OpenOpenAlexFDO

Authors Ruiwen Chen, Rahul Santhanam

Publication date 20 November 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-24318-4_4

zbMATH Keywords

MAX-SATsatisfiability algorithmMAX-\(k\)-CSP

Mathematics Subject Classification ID

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

Recommendations

• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Improved exact algorithms for mildly sparse instances of MAX SAT
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Improved exact algorithms for mildly sparse instances of MAX SAT
• New exact algorithms for the 2-constraint satisfaction problem

Cites work

• A measure \& conquer approach for the analysis of exact algorithms
• A new algorithm for optimal 2-constraint satisfaction and its implications
• 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
• An improved deterministic \#SAT algorithm for small De Morgan formulas
• Improved exact algorithms for MAX-SAT
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• 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 exact algorithms for the 2-constraint satisfaction problem
• Optimal 2-constraint satisfaction via sum-product algorithms
• Shrinkage of de Morgan formulae under restriction
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• The complexity of satisfiability of small depth circuits
• The effect of random restrictions on formula size

Cited in

(18)

• Improved exact algorithms for mildly sparse instances of MAX SAT
• Satisfiability and derandomization for small polynomial threshold circuits
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Sparsification of SAT and CSP Problems via Tractable Extensions
• The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
• scientific article; zbMATH DE number 7471677 (Why is no real title available?)
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• Probabilistic characterization of random Max \(r\)-Sat
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
• CHAMP: a multipass algorithm for Max Sat based on saver variables
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Go-MOCE: greedy order method of conditional expectations for Max Sat
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• Using the method of conditional expectations to supply an improved starting point for CCLS
• Improved exact algorithms for mildly sparse instances of MAX SAT

This page was built for publication: Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP

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