Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
Debajyoti Kar, Arindam Khan, Andreas Wiese
We study the two-dimensional (geometric) knapsack problem with rotations (2DKR), in which we are given a square knapsack and a set of rectangles with associated profits. The object…
cs.DS2025
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…
cs.DS2024
Random-Order Online Independent Set of Intervals and Hyperrectangles
Mohit Garg, Debajyoti Kar, Arindam Khan
In the Maximum Independent Set of Hyperrectangles problem, we are given a set of (possibly overlapping) -dimensional axis-aligned hyperrectangles, and the goal is to find a…