Approximating the geometric knapsack problem in near-linear time and dynamically

DOI10.4230/LIPICS.SOCG.2024.26MaRDI QIDQ6895879zbMATH OpenFDO

Authors Moritz Buchem, Paul Deuker, Andreas Wiese

Publication date 24 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2024.26

zbMATH Keywords

approximation algorithmsdynamic algorithmsgeometric packing

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Cites work

• A Fast Approximation Scheme for the Multiple Knapsack Problem
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• A PTAS for packing hypercubes into a knapsack
• A quasi-PTAS for the two-dimensional geometric knapsack problem
• Algorithm Theory - SWAT 2004
• Approximating Geometric Knapsack via L-packings
• Approximating Knapsack and partition via dense subset sums
• Approximating the geometric knapsack problem in near-linear time and dynamically
• Approximation algorithms for orthogonal packing problems for hypercubes
• Dynamic maintenance of monotone dynamic programs and applications
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem
• scientific article; zbMATH DE number 1418266 (Why is no real title available?)
• scientific article; zbMATH DE number 7204473 (Why is no real title available?)
• scientific article; zbMATH DE number 7799596 (Why is no real title available?)
• Multivariate fine-grained complexity of longest common subsequence
• On problems equivalent to \((\min,+)\)-convolution
• On the two-dimensional knapsack problem for convex polygons
• Parameterized approximation scheme for the multiple knapsack problem
• Quadratic conditional lower bounds for string problems and dynamic time warping
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• Subcubic equivalences between path, matrix and triangle problems
• Tight hardness results for LCS and other sequence similarity measures
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
• Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails

Cited in

(2)

• Approximating the geometric knapsack problem in near-linear time and dynamically
• Improved approximation algorithms for three-dimensional knapsack

This page was built for publication: Approximating the geometric knapsack problem in near-linear time and dynamically

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6895879)