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…
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…
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…
Hardness and Tight Approximations of Demand Strip Packing
Klaus Jansen, Malin Rau, Malte Tutas
We settle the pseudo-polynomial complexity of the Demand Strip Packing (DSP) problem: Given a strip of fixed width and a set of items with widths and heights, the items must be pla…
Improved Approximation Algorithms for Three-Dimensional Knapsack
Klaus Jansen, Debajyoti Kar, Arindam Khan +2
We study the three-dimensional Knapsack (3DK) problem, in which we are given a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack. The objective…
Exact and Approximate High-Multiplicity Scheduling on Identical Machines
Klaus Jansen, Kai Kahler, Esther Zwanger
Goemans and Rothvoss (SODA'14) gave a framework for solving problems which can be described as finding a point in intcone, where $P,Q\subset\mathbb{R}…