5 citations · 17 across the 11 of their papers we have counts for
5 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…
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…
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…
Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles
Monika Henzinger, Stefan Neumann, Andreas Wiese
Independent set is a fundamental problem in combinatorial optimization. While in general graphs the problem is essentially inapproximable, for many important graph classes there ar…
Approximation Schemes for Independent Set and Sparse Subsets of Polygons
Anna Adamaszek, Sariel Har-Peled, Andreas Wiese
We present an -approximation algorithm with quasi-polynomial running time for computing the maximum weight independent set of polygons out of a given set of polygo…