An approximation algorithm for \#k-SAT

DOI10.4230/LIPICS.STACS.2012.78zbMATH Open1245.68244arXiv1107.2001MaRDI QIDQ2904751FDOQ2904751

Marc Thurley

Publication date: 23 August 2012

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

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

zbMATH Keywords

approximate countingexponential algorithms\(\#k\)-SAT

Mathematics Subject Classification ID

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

Cited In (10)

• On the K‐sat model with large number of clauses
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• The relative exponential time complexity of approximate counting satisfying assignments
• On approximability of satisfiable k -CSPs: I
• Title not available (Why is that?)
• Theory and Applications of Satisfiability Testing
• Title not available (Why is that?)
• Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT

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)