2 citations · 9 across the 18 of their papers we have counts for
11 papers · 1 filter
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…
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…
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…
Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters
Matthias Bentert, Klaus Heeger, Dušan Knop
In the presented paper we study the Length-Bounded Cut problem for special graph classes as well as from a parameterized-complexity viewpoint. Here, we are given a graph , two v…