4 papers
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…
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…