4 papers · 1 filter
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…
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…
FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
Klaus Jansen, Alexandra Lassota, Malte Tutas +1
We study the computational complexity of fairly allocating indivisible, mixed-manna items. For basic measures of fairness, this problem is hard in general. Thus, research has flour…
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…