[Back]

M. Kronegger, M. Lackner, A. Pfandler, R. Pichler:
"On the Parameterized Complexity of Generalized CP-Nets";
Talk: Workshop on Challenges in Algorithmic Social Choice (CASC), Bad Belzig, Deutschland; 2014-10-08 - 2014-10-11.

Generalized CP-nets (GCP-nets) allow a succinct representation of
preferences over multi-attribute domains. As a consequence of their
succinct representation, even basic tasks for GCP-nets are
computationally hard. Even finding the more preferable of two outcomes
is PSPACE-complete. In this work, we employ the framework of
parameterized complexity to achieve two goals: First, we want to gain
a deeper understanding of the computational complexity of
GCP-nets. Second, we search for efficient fixed-parameter tractable
algorithms.

This talk is based on joint work with Martin Kronegger, Martin
Lackner, and Reinhard Pichler, which will also be presented at AAAI-14
and the PCCR workshop.

Project Head Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen