3 papers
cs.DS2018
Improved Pseudo-Polynomial-Time Approximation for Strip Packing
Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala +1
We study the strip packing problem, a classical packing problem which generalizes both bin packing and makespan minimization. Here we are given a set of axis-parallel rectangles in…
cs.DS2017
Approximation Algorithms for Rectangle Packing Problems (PhD Thesis)
Salvatore Ingala
In rectangle packing problems we are given the task of placing axis-aligned rectangles in a given plane region, so that they do not overlap with each other. In Maximum Weight Indep…
cs.DS2017
Approximating Geometric Knapsack via L-packings
Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich +3
We study the two-dimensional geometric knapsack problem (2DK) in which we are given a set of n axis-aligned rectangular items, each one with an associated profit, and an axis-align…