1 Search Results for "Zisser, Markus"

Document
DOI: 10.4230/LIPIcs.ESA.2018.28
Weighted Model Counting on the GPU by Exploiting Small Treewidth

Authors: Johannes K. Fichte, Markus Hecher, Stefan Woltran, and Markus Zisser

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We propose a novel solver that efficiently finds almost the exact number of solutions of a Boolean formula (#Sat) and the weighted model count of a weighted Boolean formula (WMC) if the treewidth of the given formula is sufficiently small. The basis of our approach are dynamic programming algorithms on tree decompositions, which we engineered towards efficient parallel execution on the GPU. We provide thorough experiments and compare the runtime of our system with state-of-the-art #Sat and WMC solvers. Our results are encouraging in the sense that also complex reasoning problems can be tackled by parameterized algorithms executed on the GPU if instances have treewidth at most 30, which is the case for more than half of counting and weighted counting benchmark instances.
Cite as

Johannes K. Fichte, Markus Hecher, Stefan Woltran, and Markus Zisser. Weighted Model Counting on the GPU by Exploiting Small Treewidth. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fichte_et_al:LIPIcs.ESA.2018.28,
  author =	{Fichte, Johannes K. and Hecher, Markus and Woltran, Stefan and Zisser, Markus},
  title =	{{Weighted Model Counting on the GPU by Exploiting Small Treewidth}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.28},
  URN =		{urn:nbn:de:0030-drops-94915},
  doi =		{10.4230/LIPIcs.ESA.2018.28},
  annote =	{Keywords: Parameterized Algorithms, Weighted Model Counting, General Purpose Computing on Graphics Processing Units, Dynamic Programming, Tree Decompositions, Treewidth}
}
  • Refine by Author
  • 1 Fichte, Johannes K.
  • 1 Hecher, Markus
  • 1 Woltran, Stefan
  • 1 Zisser, Markus

  • Refine by Classification
  • 1 Computer systems organization → Single instruction, multiple data
  • 1 Computing methodologies → Graphics processors
  • 1 Hardware → Theorem proving and SAT solving
  • 1 Theory of computation → Complexity theory and logic
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Dynamic Programming
  • 1 General Purpose Computing on Graphics Processing Units
  • 1 Parameterized Algorithms
  • 1 Tree Decompositions
  • 1 Treewidth
  • Show More...

  • 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