Showing cs.CGShow all
2 papers · 1 filter
cs.CG2021
A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangles
Waldo Gálvez, Arindam Khan, Mathieu Mari +3
We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overl…
cs.CG2021
Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More
Waldo Gálvez, Fabrizio Grandoni, Arindam Khan +2
In the \textsc{2-Dimensional Knapsack} problem (2DK) we are given a square knapsack and a collection of rectangular items with integer sizes and profits. Our goal is to find th…