2 citations · 7 across the 14 of their papers we have counts for
8 papers · 1 filter
A PTAS for the horizontal rectangle stabbing problem
Arindam Khan, Aditya Subramanian, Andreas Wiese
We study rectangle stabbing problems in which we are given axis-aligned rectangles in the plane that we want to stab, i.e., we want to select line segments such that for each g…
Universal and Tight Online Algorithms for Generalized-Mean Welfare
Siddharth Barman, Arindam Khan, Arnab Maiti
We study fair and efficient allocation of divisible goods, in an online manner, among agents. The goods arrive online in a sequence of time periods. The agents' values for…
Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing
Arindam Khan, Eklavya Sharma, K. V. N. Sreenivas
We study the generalized multidimensional bin packing problem (GVBP) that generalizes both geometric packing and vector packing. Here, we are given rectangular items where the…
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…
Peak Demand Minimization via Sliced Strip Packing
Max A. Deppert, Klaus Jansen, Arindam Khan +2
We study Nonpreemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedu…
Tight Approximation Algorithms for Geometric Bin Packing with Skewed Items
Arindam Khan, Eklavya Sharma
In the Two-dimensional Bin Packing (2BP) problem, we are given a set of rectangles of height and width at most one and our goal is to find an axis-aligned nonoverlapping packing of…
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…
On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem
Arindam Khan, Arnab Maiti, Amatya Sharma +1
In two-dimensional geometric knapsack problem, we are given a set of n axis-aligned rectangular items and an axis-aligned square-shaped knapsack. Each item has integral width, inte…