5 papers
How Hard is it to Explain Preferences Using Few Boolean Attributes?
Clemens Anzinger, Jiehua Chen, Christian Hatschka +2
We study the computational complexity of explaining preference data through Boolean attribute models (BAMs), motivated by extensive research involving attribute models and their pr…
Partitioned Combinatorial Optimization Games
Jiehua Chen, Christian Hatschka, Sofia Simola
We propose a class of cooperative games, called d Partitioned Compbinatorial Optimization Games (PCOGs). The input of PCOG consists of a set of agents and a combinatorial structure…
Multi-Organizational Scheduling: Individual Rationality, Optimality, and Complexity
Jiehua Chen, Martin Durand, Christian Hatschka
We investigate multi-organizational scheduling problems, building upon the framework introduced by Pascual et al.[2009]. In this setting, multiple organizations each own a set of i…
Computational Social Choice: Parameterized Complexity and Challenges
Jiehua Chen, Christian Hatschka, Sofia Simola
We survey two key problems-Multi-Winner Determination and Hedonic Games in Computational Social Choice, with a special focus on their parameterized complexity, and propose some res…
Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts
Cornelius Brand, Esra Ceylan, Christian Hatschka +2
Decompositional parameters such as treewidth are commonly used to obtain fixed-parameter algorithms for NP-hard graph problems. For problems that are W[1]-hard parameterized by tre…