On the two-dimensional knapsack problem for convex polygons

DOI10.4230/LIPICS.ICALP.2020.84MaRDI QIDQ6842487zbMATH OpenFDO

Authors Arturo I. Merino, Andreas Wiese

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

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

zbMATH Keywords

approximation algorithmspolygonsrotationgeometric knapsack problem

Mathematics Subject Classification ID

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

Cites work

• A Polynomial Time Approximation Scheme for the Square Packing Problem
• A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A quasi-PTAS for the two-dimensional geometric knapsack problem
• A structural lemma in 2-dimensional packing, and its implications on approximability
• Algorithm Theory - SWAT 2004
• Approximating geometric knapsack via L-packings
• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem
• New Approximability Results for 2-Dimensional Packing Problems
• On rectangle packing, maximizing benefits
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Two-dimensional knapsack for circles

Cited in

(4)

• Improved approximation algorithms for 2-dimensional knapsack: packing into multiple l-shapes, spirals, and more
• On greedily packing anchored rectangles
• Approximation schemes for geometric knapsack for packing spheres and fat objects
• Approximating the geometric knapsack problem in near-linear time and dynamically

This page was built for publication: On the two-dimensional knapsack problem for convex polygons

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