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

DOI10.1007/978-3-319-24318-4_4zbMATH Open1476.68248OpenAlexW2191626561MaRDI QIDQ3453207FDOQ3453207

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

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

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)

Cites Work

• A measure \& conquer approach for the analysis of exact algorithms
• A new algorithm for optimal 2-constraint satisfaction and its implications
• The complexity of satisfiability of small depth circuits
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• Mining circuit lower bound proofs for meta-algorithms
• The effect of random restrictions on formula size
• Shrinkage of de Morgan formulae under restriction
• An improved deterministic \#SAT algorithm for small De Morgan formulas
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• New Bounds for MAX-SAT by Clause Learning
• Optimal 2-constraint satisfaction via sum-product algorithms
• Improved exact algorithms for MAX-SAT
• New exact algorithms for the 2-constraint satisfaction problem
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time

Cited In (18)

• 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$$
• Title not available (Why is that?)
• 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
• Improved exact algorithms for mildly sparse instances of MAX SAT
• Satisfiability and derandomization for small polynomial threshold circuits

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)