Solving and sampling with many solutions: satisfiability and other hard problems

DOI10.4230/LIPICS.IPEC.2017.11MaRDI QIDQ5111870zbMATH OpenOpenAlexFDO

Authors Jean Cardinal, Jerri Nummenpalo, Emo Welzl

Publication date 27 May 2020

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

zbMATH Keywords

parameterized complexitysamplingsatisfiability

Mathematics Subject Classification ID

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

Abstract: We investigate parameterizing hard combinatorial problems by the size of the solution set compared to all solution candidates. Our main result is a uniform sampling algorithm for satisfying assignments of 2-CNF formulas that runs in expected time $O^{\ast }(varepsilo{n}^{-0.617})$ where $varepsilon$ is the fraction of assignments that are satisfying. This improves significantly over the trivial sampling bound of expected $Thet{a}^{\ast }(varepsilo{n}^{-1})$, and on all previous algorithms whenever $varepsilon=Omega(0.708^n)$. We also consider algorithms for 3-SAT with an $varepsilon$ fraction of satisfying assignments, and prove that it can be solved in $O^{\ast }(varepsilo{n}^{-2.27})$ deterministic time, and in $O^{\ast }(varepsilo{n}^{-0.936})$ randomized time. Finally, to further demonstrate the applicability of this framework, we also explore how similar techniques can be used for vertex cover problems.

Recommendations

• Solving and sampling with many solutions
• scientific article; zbMATH DE number 2090009
• Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime
• An approximation algorithm for \(\#k\)-SAT
• Why almost all satisfiable k-CNF formulas are easy

Cites work

• 3-SAT faster and simpler -- unique-SAT bounds for PPSZ hold in general
• A fast deterministic algorithm for formulas that have many satisfying assignments
• A probabilistic algorithm for k-SAT based on limited local search and restart
• A short implicant of a CNF formula with many satisfying assignments
• A short proof for a theorem of Harper about Hamming-spheres
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT
• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• Improved pseudorandom generators for depth 2 circuits
• Random generation of combinatorial structures from a uniform distribution
• Solving and sampling with many solutions: satisfiability and other hard problems
• Solving satisfiability in less than \(2^ n\) steps
• Theory and Applications of Satisfiability Testing

Cited in

(4)

• Practically uniform solution sampling in constraint programming
• Solving and sampling with many solutions
• Solving and sampling with many solutions: satisfiability and other hard problems
• Algorithms for the diverse-k-SAT problem: the geometry of satisfying assignments

This page was built for publication: Solving and sampling with many solutions: satisfiability and other hard problems

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