3 citations · 9 across the 9 of their papers we have counts for
10 papers · 1 filter
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…
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…
Single Machine Batch Scheduling to Minimize the Weighted Number of Tardy Jobs
Danny Hermelin, Matthias Mnich, Simon Omlor
The scheduling problem takes as input a batch setup time and a set of jobs, each having a processing time, a release date, a weight, and a due date; t…