Approximating Geometric Knapsack via L-packings

DOI10.1145/3473713MaRDI QIDQ5035877zbMATH OpenOpenAlexFDO

Authors Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, Sandy Heydrich, Arindam Khan, Andreas Wiese

Publication date 22 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.07710

zbMATH Keywords

approximation algorithmsgeometric knapsackrectangle packing

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• A quasi-PTAS for the two-dimensional geometric knapsack problem
• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem
• Faster approximation schemes for the two-dimensional knapsack problem
• A structural lemma in 2-dimensional packing, and its implications on approximability

Cited in

(20)

• Optimizing some constructions with bars: new geometric knapsack problems
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• Improved Online Algorithms for Knapsack and GAP in the Random Order Model
• A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing
• Tight approximation algorithms for geometric bin packing with skewed items
• Peak demand minimization via sliced strip packing
• Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints
• On improved interval cover mechanisms for crowdsourcing markets
• (Re)packing equal disks into rectangle
• Approximation schemes for geometric knapsack for packing spheres and fat objects
• Geometric Knapsack problems
• Approximating the maximum independent set of convex polygons with a bounded number of directions
• Approximating the geometric knapsack problem in near-linear time and dynamically
• Tight approximation algorithms for 2D guillotine strip packing
• A parameterized approximation scheme for the geometric knapsack problem with wide items
• Random-order online independent set of intervals and hyperrectangles
• On approximation schemes for stabbing rectilinear polygons
• Improved approximation algorithms for three-dimensional knapsack
• Improved approximation guarantees for advertisement placement
• Improved approximation algorithms for three-dimensional bin packing

This page was built for publication: Approximating Geometric Knapsack via L-packings

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