6 papers
Improved Approximation Algorithms for Parallel Task Scheduling and Multiple Cluster Scheduling
Bennet Edler, Klaus Jansen, Felix Ohnesorge +1
In the problem of Parallel Task Scheduling (PTS), we are asked to schedule jobs, each with a fixed processing time and machine requirement, such that the completion time of the…
An Analysis of Decision Problems for Relational Pattern Languages under Various Constraints
Klaus Jansen, Dirk Nowotka, Lis Pirotton +2
Patterns are words with terminals and variables. The language of a pattern is the set of words obtained by uniformly substituting all variables with words that contain only termina…
A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
Klaus Jansen, Felix Ohnesorge, Lis Pirotton
Consider a high-multiplicity Bin Packing instance with distinct item types. In 2014, Goemans and Rothvoss gave an algorithm with runtime for this problem…
The Support of Bin Packing is Exponential
Klaus Jansen, Felix Ohnesorge, Lis Pirotton +1
Consider the classical Bin Packing problem with different item sizes and amounts of items The support of a Bin Packing solution is the number of differently filled…
Minimizing the Weighted Makespan with Restarts on a Single Machine
Aflatoun Amouzandeh, Klaus Jansen, Lis Pirotton +2
We consider the problem of minimizing the weighted makespan on a single machine with restarts. Restarts are similar to preemptions but weaker: a job can be interrupted, but then it…
New Algorithm for Combinatorial -folds and Applications
Klaus Jansen, Kai Kahler, Lis Pirotton +1
Block-structured integer linear programs (ILPs) play an important role in various application fields. We address -fold ILPs where the matrix has a specific structu…