A PTAS for packing hypercubes into a knapsack

DOI10.4230/LIPICS.ICALP.2022.78MaRDI QIDQ6560875zbMATH OpenFDO

Authors Klaus Jansen, Arindam Khan, Marvin Lira, K. V. N. Sreenivas

Publication date 24 June 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2022.78

zbMATH Keywords

cube packinggeometric packingmultidimensional knapsackstrip packing

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cited in

(8)

• Approximation schemes under resource augmentation for knapsack and packing problems of hyperspheres and other shapes
• A PTAS for the horizontal rectangle stabbing problem
• Approximation schemes for geometric knapsack for packing spheres and fat objects
• Approximating the geometric knapsack problem in near-linear time and dynamically
• Approximation algorithms for round-UFP and round-SAP
• Random-order online independent set of intervals and hyperrectangles
• On approximation schemes for stabbing rectilinear polygons
• Improved approximation algorithms for three-dimensional knapsack

This page was built for publication: A PTAS for packing hypercubes into a knapsack

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