research
∙
07/31/2023
Efficient Algorithms for Monroe and CC Rules in Multi-Winner Elections with (Nearly) Structured Preferences
We investigate winner determination for two popular proportional represe...
share
research
∙
05/17/2023
Optimal Seat Arrangement: What Are the Hard and Easy Cases?
We study four NP-hard optimal seat arrangement problems [Bodlaender et a...
research
∙
02/03/2023
Optimal Capacity Modification for Many-To-One Matching Problems
We consider many-to-one matching problems, where one side consists of st...
research
∙
12/01/2022
Game Implementation: What Are the Obstructions?
In many applications, we want to influence the decisions of independent ...
research
∙
05/29/2022
2-Dimensional Euclidean Preferences
A preference profile with m alternatives and n voters is 2-dimensional E...
research
∙
03/17/2022
Cores in Friend-Oriented Hedonic Games: Verification is Surprisingly Harder than Searching
We resolve an open question by Woeginger [Open Problem 13, SOFSEM '13] r...
research
∙
02/24/2022
Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule
Answering an open question by Betzler et al. [Betzler et al., JAIR'13], ...
research
∙
01/24/2022
Multidimensional Manhattan Preferences
A preference profile with m alternatives and n voters is d-Manhattan (re...
research
∙
08/09/2021
Euclidean 3D Stable Roommates is NP-hard
We establish NP-completeness for the Euclidean 3D Stable Roommates probl...
research
∙
05/12/2021
On (Coalitional) Exchange-Stable Matching
We study (coalitional) exchange stability, which Alcalde [Economic Desig...
research
∙
04/30/2021
Participatory Budgeting with Donations and Diversity Constraints
Participatory budgeting (PB) is a democratic process where citizens join...
research
∙
11/24/2020
Fractional Matchings under Preferences: Stability and Optimality
We thoroughly study a generalized version of the classic Stable Marriage...
research
∙
05/31/2020
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
We present a data structure that in a dynamic graph of treedepth at most...
research
∙
01/27/2020
Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP
We investigate the following many-to-one stable matching problem with di...
research
∙
07/02/2019
Adapting Stable Matchings to Evolving Preferences
Adaptivity to changing environments and constraints is key to success in...
research
∙
06/28/2019
Stable Matchings in Divorce Graphs
In this paper, we study the Reaching Stable Marriage via Divorce Operati...
research
∙
05/10/2019
Good Things Come to Those Who Swap Objects on Paths
We study a simple exchange market, introduced by Gourvés, Lesca and Wilc...
research
∙
04/17/2019
Computational Complexity of Stable Marriage and Stable Roommates and Their Variants
This paper gives an overview on and summarizes existing complexity and a...
research
∙
03/14/2019
Stable Roommates with Narcissistic, Single-Peaked, and Single-Crossing Preferences
The classical Stable Roommates problem asks whether it is possible to ha...
research
∙
02/15/2019
Matchings under Preferences: Strength of Stability and Trade-offs
We propose two solution concepts for matchings under preferences: robust...
research
∙
10/15/2018
Small One-Dimensional Euclidean Preference Profiles
We characterize one-dimensional Euclidean preference profiles with a sma...
research
∙
07/24/2018
A Note on Clustering Aggregation
We consider the clustering aggregation problem in which we are given a s...
research
∙
07/17/2018
On Computing Centroids According to the p-Norms of Hamming Distance Vectors
In this paper we consider the p-Norm Hamming Centroid problem which asks...
research
∙
01/08/2018
Stable Marriage with Multi-Modal Preferences
We introduce a generalized version of the famous Stable Marriage problem...
research
∙
09/26/2017
A Parameterized View on Multi-Layer Cluster Editing
In classical Cluster Editing we seek to transform a given graph into a d...
research
∙
07/13/2017
How hard is it to satisfy (almost) all roommates?
The classical Stable Roommates problem (which is a non-bipartite general...
research
∙
11/28/2014