research
∙
08/24/2023
No Polynomial Kernels for Knapsack
This paper focuses on kernelization algorithms for the fundamental Knaps...
share
research
∙
01/02/2023
Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions
We provide a general framework to exclude parameterized running times of...
research
∙
08/08/2022
A Map of Diverse Synthetic Stable Roommates Instances
Focusing on Stable Roommates (SR) instances, we contribute to the toolbo...
research
∙
08/02/2022
Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
When computing stable matchings, it is usually assumed that the preferen...
research
∙
05/16/2022
Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences
We study stable matching problems where agents have multilayer preferenc...
research
∙
04/21/2022
Adapting Stable Matchings to Forced and Forbidden Pairs
We introduce the problem of adapting a stable matching to forced and for...
research
∙
02/03/2022
Multivariate Algorithmics for Eliminating Envy by Donating Goods
Fairly dividing a set of indivisible resources to a set of agents is of ...
research
∙
12/10/2021
Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets
Following up on purely theoretical work of Bredereck et al. [AAAI 2020],...
research
∙
10/12/2021
Popular matchings with weighted voters
In the Popular Matching problem, we are given a bipartite graph G = (A ∪...
research
∙
10/07/2021
Polynomial Turing Kernels for Clique with an Optimal Number of Queries
A polynomial Turing kernel for some parameterized problem P is a polynom...
research
∙
10/09/2020
Equitable Scheduling on a Single Machine
We introduce a natural but seemingly yet unstudied generalization of the...
research
∙
09/29/2020
Multidimensional Stable Roommates with Master List
Since the early days of research in algorithms and complexity, the compu...
research
∙
09/29/2020
A Fine-Grained View on Stable Many-To-One Matching Problems with Lower and Upper Quotas
In the Hospital Residents problem with lower and upper quotas (HR-Q^U_L)...
research
∙
07/09/2020
Bribery and Control in Stable Marriage
We initiate the study of external manipulations in Stable Marriage by co...
research
∙
12/09/2019
Multistage Graph Problems on a Global Budget
Time-evolving or temporal graphs gain more and more popularity when stud...
research
∙
12/09/2019
Multistage Problems on a Global Budget
Time-evolving or temporal graphs gain more and more popularity when stud...
research
∙
11/21/2019
Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
We continue and extend previous work on the parameterized complexity ana...
research
∙
10/08/2019
Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters
In the presented paper we study the Length-Bounded Cut problem for speci...
research
∙
07/24/2019