13 citations · 59 across the 31 of their papers we have counts for
37 papers
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…
Hardness of Interval Scheduling on Unrelated Machines
Danny Hermelin, Yuval Itzhaki, Hendrik Molter +1
We provide new (parameterized) computational hardness results for Interval Scheduling on Unrelated Machines. It is a classical scheduling problem motivated from just-in-time or lea…
Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions
Danny Hermelin, Hendrik Molter, Dvir Shabtay
The problem asks to determine -- given jobs each with its own processing time, weight, and due date -- the minimum weighted number of tardy jobs in any s…
Fairness in Repetitive Scheduling
Danny Hermelin, Hendrik Molter, Rolf Niedermeier +2
Recent research found that fairness plays a key role in customer satisfaction. Therefore, many manufacturing and services industries have become aware of the need to treat customer…
Temporal Interval Cliques and Independent Sets
Danny Hermelin, Yuval Itzhaki, Hendrik Molter +1
Temporal graphs have been recently introduced to model changes to a given network that occur throughout a fixed period of time. The Temporal Clique problem, that generalizes th…
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…