13 citations · 59 across the 31 of their papers we have counts for
6 papers · 1 filter
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…
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Jiehua Chen, Wojciech Czerwiński, Yann Disser +8
We present a data structure that in a dynamic graph of treedepth at most , which is modified over time by edge insertions and deletions, maintains an optimum-height elimination…
Approximating Sparse Quadratic Programs
Danny Hermelin, Leon Kellerhals, Rolf Niedermeier +1
Given a matrix , we consider the problem of maximizing subject to the constraint . This problem, called MaxQP by Charikar an…
Scheduling Lower Bounds via AND Subset Sum
Amir Abboud, Karl Bringmann, Danny Hermelin +1
Given instances of Subset Sum, the AND Subset Sum problem asks to determine whether all of these instances are yes-instances; that is, whether each…
Faster Minimization of Tardy Processing Time on a Single Machine
Karl Bringmann, Nick Fischer, Danny Hermelin +2
This paper is concerned with the problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental sch…
Computing the k Densest Subgraphs of a Graph
Riccardo Dondi, Danny Hermelin
Computing cohesive subgraphs is a central problem in graph theory. While many formulations of cohesive subgraphs lead to NP-hard problems, finding a densest subgraph can be done in…