1 Search Results for "Nummenpalo, Jerri"

Document
DOI: 10.4230/LIPIcs.IPEC.2017.11
Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems

Authors: Jean Cardinal, Jerri Nummenpalo, and Emo Welzl

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

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^*(eps^{-0.617}) where eps is the fraction of assignments that are satisfying. This improves significantly over the trivial sampling bound of expected Theta^*(eps^{-1}), and on all previous algorithms whenever eps = Omega(0.708^n). We also consider algorithms for 3-SAT with an eps fraction of satisfying assignments, and prove that it can be solved in O^*(eps^{-2.27}) deterministic time, and in O^*(eps^{-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.
Cite as

Jean Cardinal, Jerri Nummenpalo, and Emo Welzl. Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.IPEC.2017.11,
  author =	{Cardinal, Jean and Nummenpalo, Jerri and Welzl, Emo},
  title =	{{Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{11:1--11:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.11},
  URN =		{urn:nbn:de:0030-drops-85459},
  doi =		{10.4230/LIPIcs.IPEC.2017.11},
  annote =	{Keywords: Satisfiability, Sampling, Parameterized complexity}
}
  • Refine by Author
  • 1 Cardinal, Jean
  • 1 Nummenpalo, Jerri
  • 1 Welzl, Emo

  • Refine by Classification

  • Refine by Keyword
  • 1 Parameterized complexity
  • 1 Sampling
  • 1 Satisfiability

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact