58 citations · 239 across the 47 of their papers we have counts for
5 papers · 1 filter
Parameterized Complexity and Kernel Bounds for Hard Planning Problems
Christer Bäckström, Peter Jonsson, Sebastian Ordyniak +1
The propositional planning problem is a notoriously difficult computational problem. Downey et al. (1999) initiated the parameterized analysis of planning (with plan length as the…
Don't Be Strict in Local Search!
Serge Gaspers, Eun Jung Kim, Sebastian Ordyniak +2
Local Search is one of the fundamental approaches to combinatorial optimization and it is used throughout AI. Several local search algorithms are based on searching the k-exchange…
The Complexity of Planning Revisited - A Parameterized Analysis
Christer Baeckstroem, Yue Chen, Peter Jonsson +2
The early classifications of the computational complexity of planning under various restrictions in STRIPS (Bylander) and SAS+ (Baeckstroem and Nebel) have influenced following res…
On Finding Optimal Polytrees
Serge Gaspers, Mikko Koivisto, Mathieu Liedloff +2
Inferring probabilistic networks from data is a notoriously difficult task. Under various goodness-of-fit measures, finding an optimal network is NP-hard, even if restricted to pol…
Algorithms and Complexity Results for Exact Bayesian Structure Learning
Sebastian Ordyniak, Stefan Szeider
Bayesian structure learning is the NP-hard problem of discovering a Bayesian network that optimally represents a given set of training data. In this paper we study the computationa…