An approximation algorithm for \#k-SAT

DOI10.4230/LIPICS.STACS.2012.78MaRDI QIDQ2904751zbMATH OpenFDO

Authors Marc Thurley

Publication date 23 August 2012

Full work available at URL https://arxiv.org/abs/1107.2001

zbMATH Keywords

\(\#k\)-SATapproximate countingexponential algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Counting good truth assignments of random k-SAT formulae
• scientific article; zbMATH DE number 2090009
• An improved exponential-time algorithm for k -SAT

Cited in

(14)

• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT
• Counting good truth assignments of random k-SAT formulae
• The relative exponential time complexity of approximate counting satisfying assignments
• The relative exponential time complexity of approximate counting satisfying assignments
• scientific article; zbMATH DE number 2084758 (Why is no real title available?)
• On the K‐sat model with large number of clauses
• scientific article; zbMATH DE number 2090009 (Why is no real title available?)
• Counting solutions to random CNF formulas
• Solving and sampling with many solutions: satisfiability and other hard problems
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Theory and Applications of Satisfiability Testing
• On approximability of satisfiable k -CSPs: I
• Nearly optimal independence oracle algorithms for edge estimation in hypergraphs

This page was built for publication: An approximation algorithm for \(\#k\)-SAT

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