A parameterized approximation scheme for the 2D-Knapsack problem with wide items

Michal Pilipczuk, Mathieu Mari, Timothe Picavet

We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal…