SAT-Basierende lokale Verbesserungsmethoden
SAT-Based Local Improvement Methods (SLIM)
Wissenschaftsdisziplinen
Informatik (40%); Mathematik (60%)
Keywords
-
SAT-encodings,
Hypertree Width,
Graph Width Parameters,
Clique-Width
Strukturelle Zerlegung ist eine der erfolgreichsten Methoden, um schwere Berechnungsprobleme, die zum Beispiel beim probabilistischen Schliessen auftreten, zu lösen. Das Finden einer geeigneten strukturellen Zerlegung ist aber selbst ein schweres Problem und stellt eine grosse Herausforderung an die Entwicklung von Algorithmen dar. In diesem Forschungsprojekt schlagen wir eine neuartige Herangehensweise zum Finden struktureller Zerlegungen vor. Die Grundidee ist, mittels exakter Methoden, eine heuristisch gefundene suboptimale Zerlegung schrittweise zu verbessern. Dieser Grundidee folgend werden wir neue Zerlegungsmethoden für Graphen, Hypergraphen und anderer Strukturen entwickeln. Wir erwarten, damit bessere Zerlegungen für Eingaben zu finden, die für exakte Methoden zu gross sind. Die geplante Forschung besteht aus einer Kombination von theoretischer Analyse und der empirischen Evaluierung von Prototypen.
- Technische Universität Wien - 100%
- Martin Grohe, RWTH Aachen - Deutschland
- Matti Järvisalo, University of Helsinki - Finnland
- Mikko Koivisto, University of Helsinki - Finnland
- Sebastian Ordyniak, University of Sheffield - Großbritannien
- Marijn J. H. Heule, Carnegie Mellon University - Vereinigte Staaten von Amerika
Research Output
- 18 Zitationen
- 30 Publikationen
-
2022
Titel Weighted Model Counting with Twin-Width DOI 10.48550/arxiv.2206.01706 Typ Preprint Autor Ganian R -
2022
Titel A Dynamic MaxSAT-based Approach to Directed Feedback Vertex Sets DOI 10.48550/arxiv.2211.06109 Typ Preprint Autor Kiesel R -
2023
Titel Co-Certificate Learning with SAT Modulo Symmetries DOI 10.48550/arxiv.2306.10427 Typ Preprint Autor Kirchweger M -
2019
Titel The Parameterized Complexity of Clustering Incomplete Data DOI 10.48550/arxiv.1911.01465 Typ Preprint Autor Eiben E -
2020
Titel Turbocharging Treewidth-Bounded Bayesian Network Structure Learning DOI 10.48550/arxiv.2006.13843 Typ Journal Article Autor Szeider Stefan Journal arXiv e-prints -
2021
Titel Formalizing Graph Trail Properties in Isabelle/HOL DOI 10.48550/arxiv.2103.03607 Typ Other Autor Kovacs L -
2020
Titel On Existential MSO and Its Relation to ETH DOI 10.1145/3417759 Typ Journal Article Autor Ganian R Journal ACM Transactions on Computation Theory (TOCT) Seiten 1-32 Link Publikation -
2020
Titel Solving the Steiner Tree Problem with few Terminals DOI 10.1109/ictai50040.2020.00054 Typ Conference Proceeding Abstract Autor Fichte J Seiten 293-300 Link Publikation -
2021
Titel New width parameters for SAT and #SAT DOI 10.1016/j.artint.2021.103460 Typ Journal Article Autor Ganian R Journal Artificial Intelligence Seiten 103460 Link Publikation -
2023
Titel On the parameterized complexity of clustering problems for incomplete data DOI 10.1016/j.jcss.2022.12.001 Typ Journal Article Autor Eiben E Journal Journal of Computer and System Sciences Seiten 1-19 -
2023
Titel Are hitting formulas hard for resolution? DOI 10.1016/j.dam.2023.05.003 Typ Journal Article Autor Peitl T Journal Discrete Applied Mathematics Seiten 173-184 Link Publikation -
2023
Titel SAT-boosted Tabu Search for Coloring Massive Graphs DOI 10.1145/3603112 Typ Journal Article Autor Schidler A Journal ACM Journal of Experimental Algorithmics Seiten 1-19 Link Publikation -
2023
Titel Computing optimal hypertree decompositions with SAT DOI 10.1016/j.artint.2023.104015 Typ Journal Article Autor Schidler A Journal Artificial Intelligence Seiten 104015 Link Publikation -
2023
Titel CSP beyond tractable constraint languages DOI 10.1007/s10601-023-09362-3 Typ Journal Article Autor Dreier J Journal Constraints Seiten 450-471 Link Publikation -
2020
Titel Threshold Treewidth and Hypertree Width DOI 10.24963/ijcai.2020/263 Typ Conference Proceeding Abstract Autor Ganian R Seiten 1898-1904 Link Publikation -
2020
Titel Induction with Generalization in Superposition Reasoning DOI 10.1007/978-3-030-53518-6_8 Typ Book Chapter Autor Hajdú M Verlag Springer Nature Seiten 123-137 Link Publikation -
2020
Titel Formalizing Graph Trail Properties in Isabelle/HOL DOI 10.1007/978-3-030-53518-6_12 Typ Book Chapter Autor Kovács L Verlag Springer Nature Seiten 190-205 Link Publikation -
2022
Titel Threshold Treewidth and Hypertree Width DOI 10.1613/jair.1.13661 Typ Journal Article Autor Ganian R Journal Journal of Artificial Intelligence Research -
2021
Titel The Parameterized Complexity of Clustering Incomplete Data DOI 10.1609/aaai.v35i8.16896 Typ Journal Article Autor Eiben E Journal Proceedings of the AAAI Conference on Artificial Intelligence -
2021
Titel Turbocharging Treewidth-Bounded Bayesian Network Structure Learning DOI 10.1609/aaai.v35i5.16508 Typ Journal Article Autor Peruvemba Ramaswamy V Journal Proceedings of the AAAI Conference on Artificial Intelligence -
2022
Titel Tractable Abstract Argumentation via Backdoor-Treewidth DOI 10.1609/aaai.v36i5.20501 Typ Journal Article Autor Dvořák W Journal Proceedings of the AAAI Conference on Artificial Intelligence -
2023
Titel Circuit Minimization with QBF-Based Exact Synthesis DOI 10.1609/aaai.v37i4.25524 Typ Journal Article Autor Reichl F Journal Proceedings of the AAAI Conference on Artificial Intelligence -
2023
Titel Co-Certificate Learning with SAT Modulo Symmetries DOI 10.24963/ijcai.2023/216 Typ Conference Proceeding Abstract Autor Kirchweger M Seiten 1944-1953 -
2022
Titel Finding a Cluster in Incomplete Data DOI 10.4230/lipics.esa.2022.47 Typ Conference Proceeding Abstract Autor Eiben E Konferenz LIPIcs, Volume 244, ESA 2022 Seiten 47:1 - 47:14 -
2022
Titel PACE Solver Description: DAGer - Cutting out Cycles with MaxSAT DOI 10.4230/lipics.ipec.2022.32 Typ Conference Proceeding Abstract Autor Kiesel R Konferenz LIPIcs, Volume 249, IPEC 2022 Seiten 32:1 - 32:4 -
2022
Titel Weighted Model Counting with Twin-Width DOI 10.4230/lipics.sat.2022.15 Typ Conference Proceeding Abstract Autor Ganian R Konferenz LIPIcs, Volume 236, SAT 2022 Seiten 15:1 - 15:17 -
2022
Titel A SAT Attack on Rota's Basis Conjecture DOI 10.4230/lipics.sat.2022.4 Typ Conference Proceeding Abstract Autor Kirchweger M Konferenz LIPIcs, Volume 236, SAT 2022 Seiten 4:1 - 4:18 -
2023
Titel A SAT Solver's Opinion on the Erdős-Faber-Lovász Conjecture DOI 10.4230/lipics.sat.2023.13 Typ Conference Proceeding Abstract Autor Kirchweger M Konferenz LIPIcs, Volume 271, SAT 2023 Seiten 13:1 - 13:17 -
2023
Titel SAT-Based Generation of Planar Graphs DOI 10.4230/lipics.sat.2023.14 Typ Conference Proceeding Abstract Autor Kirchweger M Konferenz LIPIcs, Volume 271, SAT 2023 Seiten 14:1 - 14:18 -
2022
Titel SAT-Based Local Search for Plane Subgraph Partitions (CG Challenge) DOI 10.4230/lipics.socg.2022.74 Typ Conference Proceeding Abstract Autor Schidler A Konferenz LIPIcs, Volume 224, SoCG 2022 Seiten 74:1 - 74:8