DynASP2.5: Dynamic Programming on Tree Decompositions in Action
A vibrant theoretical research area are efficient exact parameterized algorithms. Very recent solving competitions such as the PACE challenge show that there is also increasing practical interest in the parameterized algorithms community. An important research question is whether dedicated parameterized exact algorithms exhibit certain practical relevance and one can even beat well-established problem solvers. We consider the logic-based declarative modeling language and problem solving framework Answer Set Programming (ASP). State-of-the-art ASP solvers rely considerably on Sat-based algorithms. An ASP solver (DynASP2), which is based on a classical dynamic programming on tree decompositions, has been published very recently. Unfortunately, DynASP2 can outperform modern ASP solvers on programs of small treewidth only if the question of interest is to count the number of solutions. In this paper, we describe underlying concepts of our new implementation (DynASP2.5) that shows competitive behavior to state-of-the-art ASP solvers even for finding just one solution when solving problems as the Steiner tree problem that have been modeled in ASP on graphs with low treewidth. Our implementation is based on a novel approach that we call multi-pass dynamic programming (M-DPSINC).
Code (1)
Tasks
Steiner Tree ProblemSimilar Papers 제목 키워드 기반
DynaSplat: Dynamic-Static Gaussian Splatting with Hierarchical Motion Decomposition for Scene Reconstruction
Reconstructing intricate, ever-changing environments remains a central ambition in computer vision, yet existing solutions often crumble before the complexity of real-world dynamics. We present DynaSplat, an approach tha…
DynaSpec: Context-aware Dynamic Speculative Sampling for Large-Vocabulary Language Models
Speculative decoding accelerates LLM inference by letting a small drafter propose multiple tokens which a large target model verifies once per speculation step. As vocabularies scale past 10e5 tokens,verification cost in…
Tree Decomposition Attention for AMR-to-Text Generation
Text generation from AMR requires mapping a semantic graph to a string that it annotates. Transformer-based graph encoders, however, poorly capture vertex dependencies that may benefit sequence prediction. To impose orde…
AMR-to-Text GenerationText GenerationDefault Logic and Bounded Treewidth
In this paper, we study Reiter's propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree d…
On Dynamic Programming Decompositions of Static Risk Measures in Markov Decision Processes
Optimizing static risk-averse objectives in Markov decision processes is difficult because they do not admit standard dynamic programming equations common in Reinforcement Learning (RL) algorithms. Dynamic programming de…
Reinforcement Learning (RL)