Solving and sampling with many solutions

DOI10.1007/s00453-019-00654-wzbMath1432.68174OpenAlexW2998625315WikidataQ126525987 ScholiaQ126525987MaRDI QIDQ2309479

Jean Cardinal, Jerri Nummenpalo, Ermo Welzl

Publication date: 1 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00654-w

zbMATH Keywords

samplingsatisfiabilityparameterizationSATCNF

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomized algorithms for 3-SAT
• Random generation of combinatorial structures from a uniform distribution
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• New upper bound for the \#3-SAT problem
• Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Improved Pseudorandom Generators for Depth 2 Circuits
• Applications of a Planar Separator Theorem
• A fast deterministic algorithm for formulas that have many satisfying assignments
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• 3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General