Showing 2024Show all
3 papers · 1 filter
cs.CG2024
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…
cs.DS2024
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…
cs.CG2024
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…