5 papers
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…
Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects
Pritam Acharya, Sujoy Bhore, Aaryan Gupta +3
We study the geometric knapsack problem in which we are given a set of -dimensional objects (each with associated profits) and the goal is to find the maximum profit subset that…
Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
Moritz Buchem, Paul Deuker, Andreas Wiese
An important goal in algorithm design is determining the best running time for solving a problem (approximately). For some problems, we know the optimal running time, assuming cert…
On Approximation Schemes for Stabbing Rectilinear Polygons
Arindam Khan, Aditya Subramanian, Tobias Widmann +1
We study the problem of stabbing rectilinear polygons, where we are given rectilinear polygons in the plane that we want to stab, i.e., we want to select horizontal line segmen…
A -approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds
Moritz Buchem, Katja Ettmayr, Hugo Kooki Kasuya Rosado +1
For a given set of points in a metric space and an integer , we seek to partition the given points into clusters. For each computed cluster, one typically defines one point…