2 citations · 9 across the 18 of their papers we have counts for
27 papers
Approximate Total Weighted Completion Time with Convex Controllable Processing Times
Klaus Heeger, Danny Hermelin, Dvir Shabtay
We study the single-machine scheduling problem with controllable processing times to minimize the total weighted completion time, focusing on the setting where a job's processing t…
Scheduling Tasks towards Energy Autarky: Benefits and Computational Costs of Flexibility
Robert Bredereck, Till Fluschnik, Klaus Heeger
We study the autarky problem: given an energy forecast, a battery, and a set of energy-consuming jobs with time windows, decide whether all jobs can be scheduled without requiring…
Fair Repetitive Interval Scheduling
Klaus Heeger, Danny Hermelin, Yuval Itzhaki +2
Fair resource allocation is undoubtedly a crucial factor in customer satisfaction in several scheduling scenarios. This is especially apparent in repetitive scheduling models where…
Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines
Klaus Heeger, Hendrik Molter
In this work, we study the computational (parameterized) complexity of . Here, we are given identical parallel machines and jobs with…
Minimizing the Number of Tardy Jobs and Maximal Tardiness on a Single Machine is NP-hard
Klaus Heeger, Danny Hermelin, Michael L. Pinedo +1
This paper resolves a long-standing open question in bicriteria scheduling regarding the complexity of a single machine scheduling problem which combines the number of tardy jobs a…
Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
Matthias Bentert, Klaus Heeger, Tomohiro Koana
We study the computational complexity of several polynomial-time-solvable graph problems parameterized by vertex integrity, a measure of a graph's vulnerability to vertex removal i…
Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
Klaus Heeger, Danny Hermelin
We consider the problem, the problem of minimizing the weighted number of tardy jobs on a single machine. This problem is one of the most basic and fundamental pr…
No Polynomial Kernels for Knapsack
Klaus Heeger, Danny Hermelin, Matthias Mnich +1
This paper focuses on kernelization algorithms for the fundamental Knapsack problem. A kernelization algorithm (or kernel) is a polynomial-time reduction from a problem onto itself…
Threshold Testing and Semi-Online Prophet Inequalities
Martin Hoefer, Kevin Schewior
We study threshold testing, an elementary probing model with the goal to choose a large value out of i.i.d. random variables. An algorithm can test each variable once for…
Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions
Klaus Heeger, André Nichterlein, Rolf Niedermeier
We provide a general framework to exclude parameterized running times of the form for problems that have polynomial running time lower bounds under hypotheses from…
A Map of Diverse Synthetic Stable Roommates Instances
Niclas Boehmer, Klaus Heeger, Stanisław Szufa
Focusing on Stable Roommates (SR) instances, we contribute to the toolbox for conducting experiments for stable matching problems. We introduce a polynomial-time computable pseudom…
Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
Niclas Boehmer, Klaus Heeger, Rolf Niedermeier
When computing stable matchings, it is usually assumed that the preferences of the agents in the matching market are fixed. However, in many realistic scenarios, preferences change…
Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences
Matthias Bentert, Niclas Boehmer, Klaus Heeger +1
We study stable matching problems where agents have multilayer preferences: There are layers each consisting of one preference relation for each agent. Recently, Chen et al.…
Adapting Stable Matchings to Forced and Forbidden Pairs
Niclas Boehmer, Klaus Heeger
We introduce the problem of adapting a stable matching to forced and forbidden pairs. Specifically, given a stable matching , a set of forced pairs, and a set of forbi…
Multivariate Algorithmics for Eliminating Envy by Donating Goods
Niclas Boehmer, Robert Bredereck, Klaus Heeger +2
Fairly dividing a set of indivisible resources to a set of agents is of utmost importance in some applications. However, after an allocation has been implemented the preferences of…
Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets
Niclas Boehmer, Klaus Heeger, Rolf Niedermeier
Following up on purely theoretical work of Bredereck et al. [AAAI 2020], we contribute further theoretical insights into adapting stable two-sided matchings to change. Moreover, we…
Polynomial Turing Kernels for Clique with an Optimal Number of Queries
Till Fluschnik, Klaus Heeger, Danny Hermelin
A polynomial Turing kernel for some parameterized problem is a polynomial-time algorithm that solves using queries to an oracle of whose sizes are upper-bounded by some…
Popular matchings with weighted voters
Klaus Heeger, Ágnes Cseh
In the Popular Matching problem, we are given a bipartite graph and for each vertex , strict preferences over the neighbors of . Given two matc…
Equitable Scheduling on a Single Machine
Klaus Heeger, Danny Hermelin, George B. Mertzios +3
We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalizati…
Multidimensional Stable Roommates with Master List
Robert Bredereck, Klaus Heeger, Dušan Knop +1
Since the early days of research in algorithms and complexity, the computation of stable matchings is a core topic. While in the classic setting the goal is to match up two agents…
A Fine-Grained View on Stable Many-To-One Matching Problems with Lower and Upper Quotas
Niclas Boehmer, Klaus Heeger
In the Hospital Residents problem with lower and upper quotas (), the goal is to find a stable matching of residents to hospitals where the number of residents matched to…
Bribery and Control in Stable Marriage
Niclas Boehmer, Robert Bredereck, Klaus Heeger +1
We initiate the study of external manipulations in Stable Marriage by considering several manipulative actions as well as several manipulation goals. For instance, one goal is to m…
Multistage Graph Problems on a Global Budget
Klaus Heeger, Anne-Sophie Himmel, Frank Kammer +3
Time-evolving or temporal graphs gain more and more popularity when studying the behavior of complex networks. In this context, the multistage view on computational problems is amo…
Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
Robert Bredereck, Klaus Heeger, Dušan Knop +1
We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier…