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.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.DS2023
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…