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…